Finite Automata and Regular Expressions

Flashcards covering foundational topics in formal automata theory including DFA, NFA, Epsilon-NFA, state transition functions, 5-tuple representations, and equivalence rules.

Finite Automaton (FA)

A computing model consisting of a finite set of states and a set of transitions from state to state that occur on input symbols chosen from an alphabet ̣\Sigma.

5-tuple Representation of FA

The formal representation of a finite automaton given by $(Q, \Sigma, \delta, q_0, F)$, where $Q$ is a finite non-empty set of states, $\Sigma$ is a finite non-empty set of input alphabets, $\delta$ is the transition function, $q_0 \in Q$ is the initial state, and $F \subseteq Q$ is the set of final states.

FA without Output

A category of finite automata (including DFA, NFA, and $\varepsilon\text{-NFA}$) whose purpose is to recognize languages by accepting or rejecting input sequences.

FA with Output

A category of finite automata (including Moore Machine and Mealy Machine) designed to model systems that generate responses as a sequence of output symbols.

Deterministic Finite Automata (DFA)

A finite automaton in which the transitions from one state to another state are deterministic, meaning the next state is uniquely known for every symbol read.

DFA Transition Function

The mapping function defined as $\delta: Q \times \Sigma \rightarrow Q$, which specifies exactly one next state for a current state and input symbol.

DFA Transition Rule

The requirement that every state in a DFA must have a defined transition for each input symbol from $\Sigma$, and $\varepsilon$ is not allowed as an input symbol.

Non-Deterministic Finite Automata (NFA)

A finite automaton in which transitions from a given state for a given input symbol can lead to more than one possible next state.

NFA Transition Function

The mapping function defined as $\delta: Q \times \Sigma \rightarrow 2^Q$, which maps a state and input symbol to a subset of states.

State Limit in NFA to DFA Conversion

If an NFA has $n$ states, then its equivalent DFA can have at most $2^n$ states.

DFA Final State Rule in NFA Conversion

During NFA to DFA conversion, any DFA composite state that contains at least one final state of the NFA becomes a final state of the DFA.

Automata Equivalence Condition

Two finite automata are not equivalent if for any pair of states $\text{\{}q_a, q_b\text{\}}$ reached on input $a \in \Sigma$, one is an intermediate state and the other is a final state, or if the initial state is a final state in only one automaton.

Epsilon NFA ($\varepsilon\text{-NFA}$)

A non-deterministic finite automaton in which transitions can occur either on input symbols or without consuming any input symbol.

Epsilon Transition ($\varepsilon\text{-transition}$)

A transition (also known as an $\varepsilon\text{-move}$ or null move) in an automaton that occurs without reading or consuming any input symbol.

Transition Function of $\varepsilon\text{-NFA}$

The transition function given by $\delta: Q \times (\Sigma \cup \{\varepsilon\}) \rightarrow 2^Q$.