1. Deterministic Finite Automaton (DFA)

A DFA consists of a finite set of states and a set of transitions that determine the next state for each pair of a current state and an input symbol. In a DFA, for every state and symbol, there is exactly one possible next state.

Q: Finite set of states
Σ: Input alphabet
δ: Transition function (δ: Q × Σ → Q)
q0: Initial state
F: Set of accept states

A string is accepted by a DFA if, starting from the initial state q0, the string leads to a state in F after processing each symbol according to δ.

2. Nondeterministic Finite Automaton (NFA)

An NFA is similar to a DFA but allows for multiple possible next states for each pair of a current state and an input symbol, including transitions with no input symbol (ε-transitions). This means an NFA can "guess" the correct path through the automaton to accept a string.

Q: Finite set of states
Σ: Input alphabet, extended by ε
δ: Transition function (δ: Q × (Σ ∪ {ε}) → P(Q))
q0: Initial state
F: Set of accept states

A string is accepted by an NFA if any sequence of transitions leads to a state in F.

3. Regular Expressions (RE)

Regular expressions are used to define the same set of strings as DFAs and NFAs. They provide a more compact and often easier way to specify patterns of text. Regular operations include union (|), concatenation, and Kleene star (*).

Examples:
a|b: Strings that are either 'a' or 'b'.
ab: Strings that start with 'a' followed by 'b'.
a*: Zero or more repetitions of 'a'.

4. Mealy and Moore Machines

Both are types of finite state machines used in designing sequential logic circuits, with outputs depending on the current state and possibly the input (Mealy) or solely on the state (Moore).

Mealy Machine:
Output depends on both state and input.
Transition function: δ: Q × Σ → Q
Output function: λ: Q × Σ → Σ
Moore Machine:
Output depends only on state.
Transition function: δ: Q × Σ → Q
Output function: λ: Q → Σ

5. Context-Free Grammar (CFG) and Pushdown Automaton (PDA)

CFG is a way to describe context-free languages, which can generate strings that cannot be described by regular expressions (like nested structures). A PDA is like an NFA but with a stack, allowing it to handle context-free languages.

CFG:
Variables, terminals, rules, start symbol.
S → aSb | ε (Generates balanced parentheses)
PDA:
States, input alphabet, stack alphabet, transition function, initial state, initial stack symbol, accept states.

                    - **DFA (Deterministic Finite Automaton)**: A machine that processes a sequence of inputs from a finite set and changes states deterministically based on the current input and state.
                    
                    - **NFA (Nondeterministic Finite Automaton)**: A machine that can be in multiple states at once, with transitions depending on the input potentially leading to several possible states.
                    
                    - **FA (Finite Automaton)**: An abstract machine used in computing for modeling computation, characterized by a finite number of states.
                    
                    - **Grammar**: A set of rules that define the structure of a language, specifying how symbols can be combined to produce valid strings.
                    
                    - **Mealy Machine**: A finite state machine where the outputs are determined by the current state and the input.
                    
                    - **Moore Machine**: A finite state machine where the outputs are determined solely by the current state.
                    
                    - **PDA (Pushdown Automaton)**: A type of automaton that uses a stack to store additional information, allowing it to recognize context-free languages.
                    
                    - **Regular Expression**: A notation for describing sets of strings through patterns that involve choices, repetition, and order.
                    
                    - **CFG (Context-Free Grammar)**: A grammar that generates all the strings of a context-free language, using rules that replace variables with combinations of variables and terminals.
                    
                    - **CFL (Context-Free Language)**: A language that can be generated by some context-free grammar, characterized by more complex structures than regular languages.