Grammars, DFA, NFA, Subset Construction & Regular Expressions
Idea in plain words
Phrase-Structure Grammar G = (V, T, S, P): V is variables, T is terminals, S is start symbol, P is production rules.
Exam tip
High-yield exam topic (Very High).
Explanation
Finite automata and formal language theory define the boundary of machine computability with finite memory. DFAs serve as the execution engine for lexical analyzers (lex/flex), regular expression pattern matching engines, network protocol state machines, and digital circuit controllers.
Key points
- Chomsky Hierarchy: Type 0 (Unrestricted), Type 1 (Context-Sensitive), Type 2 (Context-Free - CFG, pushdown automata), Type 3 (Regular - finite automata).
- Deterministic Finite Automaton (DFA): 5-tuple M = (Q, Σ, δ, q₀, F) where transition δ: Q × Σ → Q is single-valued.
- Non-Deterministic Finite Automaton (NFA): δ: Q × Σ → P(Q). Can transition to zero, one, or multiple states, or via λ/ε without reading input.
- Equivalence of DFA and NFA: Every NFA can be converted to an equivalent DFA using the Subset Construction (Powerset Construction) algorithm.
- Pumping Lemma: If L is regular, any string s ∈ L with |s| ≥ p can be partitioned into s = xyz such that |y| > 0, |xy| ≤ p, and xy^i z ∈ L for all i ≥ 0. Used to prove languages non-regular (e.g., L = {a^n b^n | n ≥ 0}).
Example
Example
Proof that L = {0^n 1^n | n ≥ 0} is NOT regular using Pumping Lemma: Assume L is regular with pumping length p. Choose s = 0^p 1^p ∈ L. Then s = xyz with |xy| ≤ p and |y| > 0. Since |xy| ≤ p, y consists entirely of 0s (y = 0^k, k ≥ 1). Pump i = 2: x y² z = 0^{p+k} 1^p. The number of 0s is p + k > p, but number of 1s is p. Thus x y² z ∉ L, creating a contradiction! Hence L is non-regular.
Code examples
// DFA State Transition Table for Language over {0, 1} ending with '01'
// States: Q = {q0 (start), q1, q2 (accept)}
//
// Present State | Input 0 | Input 1
// --------------+---------+--------
// -> q0 | q1 | q0
// q1 | q1 | q2 (Accepting)
// *q2 | q1 | q0
//
// Tracing string "1101":
// δ(q0, 1) = q0
// δ(q0, 1) = q0
// δ(q0, 0) = q1
// δ(q1, 1) = q2 ∈ F (String is ACCEPTED)
Exam questions
- [8 Marks] Design a DFA that accepts the language over Σ = {a, b} consisting of all strings containing 'aba' as a substring. Show transition table and state diagram.
- [8 Marks] Convert a given NFA with transitions δ(q0, a)={q0, q1}, δ(q0, b)={q0}, δ(q1, b)={q2} into an equivalent DFA using subset construction.
- [7 Marks] State the Pumping Lemma for regular languages. Use it to prove that L = {a^n b^n | n ≥ 1} is not regular.