Unit 1: Finite Automata and Regular Languages

1. Mathematical Foundations: Alphabets, Strings, and Languages

The theory of computation investigates the fundamental capabilities and limitations of abstract computing devices. Before formalizing abstract machines, we must establish rigorous mathematical definitions for symbols, sequences, and computational problems.

1.1 Core Mathematical Definitions

• Symbol: An indivisible, atomic character, token, or digit (e.g., $0, 1, a, b$).
• Alphabet ($\Sigma$): A finite, non-empty set of symbols.
  • Binary Alphabet: $\Sigma = \{0, 1\}$
  • Lowercase English Alphabet: $\Sigma = \{a, b, c, \dots, z\}$
  • Decimal Alphabet: $\Sigma = \{0, 1, 2, \dots, 9\}$
• String (Word, $w$): A finite sequence of symbols chosen from an alphabet $\Sigma$.
  • Example: If $\Sigma = \{a, b\}$, then $w = aabab$ is a string over $\Sigma$.
• Length of a String ($|w|$): The number of symbol positions in $w$.
  • If $w = aabab$, then $|w| = 5$.
  • The number of occurrences of a specific symbol $a$ in $w$ is denoted $|w|_a$. Here, $|aabab|_a = 3$.
• Empty String ($\epsilon$ or $\lambda$): The unique string containing zero symbols. Its length is zero:
  $|\epsilon| = 0$
  For any string $w$, the empty string acts as the identity element under concatenation:
  $w\epsilon = \epsilon w = w$
• Powers of an Alphabet ($\Sigma^k$): The set of all strings of exact length $k$ formed from symbols of $\Sigma$.
  • $\Sigma^0 = \{\epsilon\}$
  • If $\Sigma = \{0, 1\}$, then $\Sigma^1 = \{0, 1\}$, $\Sigma^2 = \{00, 01, 10, 11\}$, and $|\Sigma^k| = |\Sigma|^k$.
• Kleene Star ($\Sigma^*$): The set of all possible finite-length strings over $\Sigma$, including the empty string:
  $\Sigma^* = \bigcup_{k=0}^{\infty} \Sigma^k = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup \dots$
  $\Sigma^*$ is an countably infinite set for any non-empty alphabet $\Sigma$.
• Positive Closure ($\Sigma^+$): The set of all non-empty strings over $\Sigma$:
  $\Sigma^+ = \bigcup_{k=1}^{\infty} \Sigma^k = \Sigma^* \setminus \{\epsilon\}$
• Language ($L$): A mathematical language over an alphabet $\Sigma$ is any subset of $\Sigma^*$:
  $L \subseteq \Sigma^*$
  • Finite Language: $L_1 = \{0, 01, 001\}$
  • Infinite Language: $L_2 = \{0^n 1^n \mid n \ge 0\} = \{\epsilon, 01, 0011, 000111, \dots\}$
  • Empty Language: $\emptyset = \{\}$ (contains zero strings; note that $\emptyset \ne \{\epsilon\}$).

1.2 Operations on Languages

Given two languages $L_1, L_2 \subseteq \Sigma^*$:

1. Union: $L_1 \cup L_2 = \{w \mid w \in L_1 \text{ or } w \in L_2\}$
2. Intersection: $L_1 \cap L_2 = \{w \mid w \in L_1 \text{ and } w \in L_2\}$
3. Concatenation: $L_1 L_2 = \{uv \mid u \in L_1, v \in L_2\}$
4. Complementation: $\overline{L} = \Sigma^* \setminus L$
5. Reversal: $L^R = \{w^R \mid w \in L\}$, where $(a_1 a_2 \dots a_n)^R = a_n \dots a_2 a_1$ and $\epsilon^R = \epsilon$.
6. Kleene Star of a Language: $L^* = \bigcup_{i=0}^{\infty} L^i$, where $L^0 = \{\epsilon\}$ and $L^i = L L^{i-1}$.

2. Overview and Structural Components of Finite Automata

A Finite Automaton (FA) is the simplest formal computational model. It possesses a strictly bounded, finite internal memory represented by discrete states. An FA inspects a sequence of input symbols sequentially from left to right, transitioning between internal states. Because its memory cannot scale with input length, a finite automaton cannot perform arbitrary unbounded counting.

2.1 Hardware Abstraction Components

1. Input Tape: A linear tape divided into cells, each storing a single symbol $a \in \Sigma$. The string terminates with an end-of-input marker.
2. Read Head: Inspects one cell at a time and advances strictly from left to right (unidirectional, read-only). It cannot write to the tape or move backward.
3. Finite Control: A set of internal states and transition logic that reads the current symbol under the head, looks up the transition function, and updates the automaton's internal state.

3. Deterministic Finite Automata (DFA)

A Deterministic Finite Automaton (DFA) is a machine in which every state has exactly one deterministic transition for each symbol of the alphabet.

3.1 Formal 5-Tuple Definition

Formally, a DFA is defined as a 5-tuple:
$M = (Q, \Sigma, \delta, q_0, F)$

Where:

• $Q$: A finite, non-empty set of internal states.
• $\Sigma$: A finite input alphabet.
• $\delta$: The transition function mapping a state and an input symbol to exactly one next state:
  $\delta: Q \times \Sigma \to Q$
• $q_0$: The initial (start) state, where $q_0 \in Q$.
• $F$: The set of final (accepting) states, where $F \subseteq Q$.

3.2 Extended Transition Function ($\hat{\delta}$)

To describe how a DFA processes entire strings rather than individual symbols, we define the extended transition function $\hat{\delta}: Q \times \Sigma^* \to Q$ recursively:

1. Basis: For the empty string $\epsilon$:
   $\hat{\delta}(q, \epsilon) = q$
2. Induction: For any string $w = xa$ where $x \in \Sigma^*$ and $a \in \Sigma$:
   $\hat{\delta}(q, xa) = \delta(\hat{\delta}(q, x), a)$

3.3 Language Acceptance

A string $w \in \Sigma^*$ is accepted by a DFA $M$ if and only if processing $w$ from the start state ends in an accepting state:
$w \in L(M) \iff \hat{\delta}(q_0, w) \in F$
The language recognized by $M$ is:
$L(M) = \{w \in \Sigma^* \mid \hat{\delta}(q_0, w) \in F\}$

CODECopy Code
+-----------------------------------------------------------------------------------+
|               DFA State Transition Diagram: Strings Ending in "01"                |
|                                                                                   |
|            +--------- 1 ---------+                                                |
|            |                     |                                                |
|            v     0         1     |                                                |
|  --> (( q0 )) -----> ( q1 ) -----> ((( q2 )))                                     |
|        ^   ^           |             |                                            |
|        |   +--- 0 -----+             |                                            |
|        |                             |                                            |
|        +-------------- 1 ------------+                                            |
|                                                                                   |
|  Alphabet: {0, 1} | Start: q0 | Accepting: {q2}                                   |
+-----------------------------------------------------------------------------------+

4. Non-Deterministic Finite Automata (NFA and $\epsilon$-NFA)

In a Non-Deterministic Finite Automaton (NFA), the machine can transition to zero, one, or multiple next states for a given state and input symbol. Conceptually, an NFA explores all possible execution paths simultaneously in parallel (or guesses the correct path non-deterministically).

4.1 Formal Definition of an NFA

An NFA is defined as a 5-tuple:
$M = (Q, \Sigma, \delta, q_0, F)$

Where:

• $\delta$ is the transition function mapping a state and a symbol to a subset of states (an element of the powerset $2^Q$):
  $\delta: Q \times \Sigma \to 2^Q$
• Acceptance condition: A string $w$ is accepted if at least one computation path terminates in an accepting state:
  $w \in L(M) \iff \hat{\delta}(q_0, w) \cap F \ne \emptyset$

4.2 NFA with $\epsilon$-Transitions ($\epsilon$-NFA)

An $\epsilon$-NFA allows transitions between states spontaneously without consuming any input symbol:
$\delta: Q \times (\Sigma \cup \{\epsilon\}) \to 2^Q$

$\epsilon$-Closure Definition

For any state $q \in Q$, the $\epsilon$-closure of $q$, denoted $\epsilon\text{-CLOSURE}(q)$, is the set of all states reachable from $q$ by following zero or more $\epsilon$-transitions:

1. $q \in \epsilon\text{-CLOSURE}(q)$ (reflexive basis).
2. If $p \in \epsilon\text{-CLOSURE}(q)$ and $r \in \delta(p, \epsilon)$, then $r \in \epsilon\text{-CLOSURE}(q)$.

For a set of states $S \subseteq Q$:
$\epsilon\text{-CLOSURE}(S) = \bigcup_{q \in S} \epsilon\text{-CLOSURE}(q)$

5. Equivalence of DFA and NFA: The Subset Construction

A foundational theorem in automata theory (proven by Michael O. Rabin and Dana Scott, 1959) establishes that NFAs, $\epsilon$-NFAs, and DFAs have identical computational expressive power. Every language accepted by an NFA can be accepted by an equivalent DFA.

5.1 The Subset Construction (Powerset Construction) Algorithm

Given an NFA $M = (Q, \Sigma, \delta_N, q_0, F_N)$, we construct an equivalent DFA $M' = (Q', \Sigma, \delta_D, q_0', F_D)$:

1. States of DFA ($Q'$): Each state in the DFA represents a subset of states of the NFA:
   $Q' \subseteq 2^Q$
   If the NFA has $n = |Q|$ states, the DFA has at most $2^n$ states.
2. Start State ($q_0'$):
   $q_0' = \epsilon\text{-CLOSURE}(q_0)$
3. Transition Function ($\delta_D$): For any DFA state $S \in Q'$ and input symbol $a \in \Sigma$:
   $\delta_D(S, a) = \epsilon\text{-CLOSURE}\left( \bigcup_{q \in S} \delta_N(q, a) \right)$
4. Accepting States ($F_D$): Any DFA state $S$ that contains at least one accepting state of the original NFA is an accepting state in the DFA:
   $F_D = \{S \in Q' \mid S \cap F_N \ne \emptyset\}$

5.2 Worst-Case State Complexity

For the language $L_k$ of strings over $\{0, 1\}$ where the $k$-th symbol from the end is a '1':

• An NFA requires only $k + 1$ states.
• The minimal equivalent DFA strictly requires $2^k$ states.
  This proves that non-determinism provides exponential succinctness in state representation, even though computational language power is identical.

6. Regular Languages and Closure Properties

A language $L \subseteq \Sigma^*$ is defined to be Regular if and only if there exists a finite automaton (DFA, NFA, or $\epsilon$-NFA) such that $L = L(M)$.

6.1 Closure Properties of Regular Languages

Regular languages form a Boolean algebra closed under the following fundamental operations:

7. Finite Automata with Output: Mealy and Moore Machines

Standard DFAs and NFAs act as Language Recognizers (yielding a binary accept/reject decision). In practical hardware design (sequential circuits, parity checkers, traffic light controllers), finite state machines must generate an output sequence associated with states or transitions.

7.1 Moore Machines

In a Moore Machine, the output depends exclusively on the current state:
$M = (Q, \Sigma, \Delta, \delta, \lambda, q_0)$
Where:

• $\Delta$: Finite output alphabet.
• $\delta: Q \times \Sigma \to Q$: State transition function.
• $\lambda: Q \to \Delta$: Output function mapping each state to an output symbol.
• Output Length: For an input string of length $n$, a Moore machine produces an output sequence of length $n + 1$, because it emits an output symbol for the initial state before processing any input.

7.2 Mealy Machines

In a Mealy Machine, the output depends both on the current state and the current input symbol:
$M = (Q, \Sigma, \Delta, \delta, \lambda, q_0)$
Where:

• $\lambda: Q \times \Sigma \to \Delta$: Output function mapping a state-symbol transition to an output symbol.
• Output Length: For an input string of length $n$, a Mealy machine produces an output sequence of length $n$.

7.3 Equivalence and Conversion Between Moore and Mealy Machines

Moore and Mealy machines are computationally equivalent: any language translation performed by a Moore machine can be performed by a Mealy machine, and vice-versa.

• Converting Moore to Mealy: Retain states and transitions; set the output of each transition edge entering state $q$ to the output assigned to state $q$ in the Moore machine:
  $\lambda_{\text{Mealy}}(p, a) = \lambda_{\text{Moore}}(\delta(p, a))$
• Converting Mealy to Moore: If a state $q$ in a Mealy machine receives transitions emitting different outputs, $q$ is split into multiple duplicate states $q_x$, each dedicated to emitting a single specific output $x \in \Delta$.

8. Minimization of Finite Automata

Given a regular language $L$, there are infinitely many distinct DFAs that recognize $L$. However, by the Myhill-Nerode Theorem, there exists a unique minimal DFA (up to state renaming/isomorphism) having the fewest possible states.

Minimizing a DFA reduces hardware circuit complexity and memory footprint in lexical analyzers (e.g., Lex/Flex).

8.1 State Equivalence Criteria

Two states $p, q \in Q$ are said to be equivalent ($p \sim q$) if for all possible input strings $w \in \Sigma^*$, both states lead either to an accepting state or both lead to a non-accepting state:
$p \sim q \iff \forall w \in \Sigma^*, (\hat{\delta}(p, w) \in F \iff \hat{\delta}(q, w) \in F)$
If there exists even one string $w$ such that $\hat{\delta}(p, w) \in F$ while $\hat{\delta}(q, w) \notin F$, the states are distinguishable ($p \not\sim q$).

8.2 The Table-Filling Algorithm (Myhill-Nerode Minimization)

1. Pre-processing (Eliminate Unreachable States): Perform a graph traversal (BFS/DFS) starting from $q_0$. Discard all unreachable states.
2. Step 1 (Base Case - Distinguish Accepting from Non-Accepting):
   Create a triangular table of all unordered state pairs $(p, q)$. Mark pair $(p, q)$ if one state is in $F$ and the other is not in $F$:
   $p \in F \text{ and } q \notin F \implies \text{Mark } (p, q)$
3. Step 2 (Inductive Marking):
   Repeat until no new marks can be placed:
   For every unmarked pair $(p, q)$ and every symbol $a \in \Sigma$:
   Compute $p' = \delta(p, a)$ and $q' = \delta(q, a)$.
   If the pair $(p', q')$ is already marked, mark $(p, q)$.
4. Step 3 (State Partitioning and Merging):
   Any state pairs remaining unmarked at the end of the algorithm are equivalent ($p \sim q$). Merge equivalent pairs into unified composite states to construct the minimal DFA.