Unit I - Automata Theory
Basic machine, FSM, DFA, NDFA, Mealy & Moore machines, Regular expressions, and Pumping Lemma
1. Basic Machine & Finite State Machine (FSM)
A Finite State Machine (FSM) is a mathematical model of computation consisting of a finite number of states and transitions between those states based on input symbols. It's the simplest computational model used to design both computer programs and sequential logic circuits.
What is a Machine?
In computer science, a machine is an abstract model that reads input, processes it, and produces output. The basic machine has:
- Input mechanism
- Processing unit
- Memory (finite or infinite)
- Output mechanism
Components of FSM:
- States (Q): A finite set of states the machine can be in at any time
- Input Alphabet (Σ): A finite set of input symbols
- Transition Function (δ): Defines how the machine moves from one state to another based on input
- Initial State (q₀): The starting state where computation begins
- Final States (F): Set of accepting/final states
Real-World Example: Traffic Light System
A traffic light is a simple FSM with:
- States: Red, Yellow, Green
- Input: Timer signal
- Transitions: Red → Green → Yellow → Red
- Initial State: Red
Types of FSM:
- Acceptors/Recognizers: Determine if input string belongs to a language
- Transducers: Produce output for given input (Mealy & Moore machines)
2. Transition Graph
A Transition Graph is a visual representation of a finite automaton using a directed graph where:
Components:
- Nodes (Circles): Represent states
- Edges (Arrows): Represent transitions labeled with input symbols
- Initial State: Indicated by an incoming arrow from nowhere
- Final States: Shown with double circles
Example: FSM accepting strings with even number of 1's
States: q₀ (even 1's - final), q₁ (odd 1's)
Input alphabet: {0, 1}
Transition Graph:
0 1 1 0
→ ((q₀)) ←→ (q₁) [Loop on both with respective inputs]
Final
Working:
- Start at q₀ (even count = 0)
- On input '1': go to q₁ (odd count)
- On another '1': return to q₀ (even count)
- On input '0': stay in same state (doesn't affect count)
3. Transition Matrix (Transition Table)
A Transition Matrix or Transition Table is a tabular representation of the transition function. It shows the next state for each combination of current state and input symbol.
Format:
- Rows represent current states
- Columns represent input symbols
- Cells contain next state(s)
Example: Transition Table for even 1's acceptor
| Current State | Input: 0 | Input: 1 |
|---|---|---|
| → q₀ (Final) | q₀ | q₁ |
| q₁ | q₁ | q₀ |
Reading the table:
- If in state q₀ and read '0' → stay in q₀
- If in state q₀ and read '1' → move to q₁
- If in state q₁ and read '1' → move to q₀
Advantages:
- Easy to implement in programming (2D array)
- Quick lookup of transitions
- Compact representation for small automata
4. Deterministic Finite Automata (DFA)
A Deterministic Finite Automaton (DFA) is a finite state machine where for each state and input symbol, there is exactly ONE transition to a next state.
Formal Definition of DFA:
A DFA is a 5-tuple M = (Q, Σ, δ, q₀, F) where:
- Q: Finite set of states
- Σ: Finite input alphabet
- δ: Q × Σ → Q: Transition function (single next state)
- q₀ ∈ Q: Initial state
- F ⊆ Q: Set of final/accepting states
Key Characteristics of DFA:
- Deterministic: No ambiguity - exactly one path for each input string
- No ε-transitions: Cannot move without consuming input
- Total Function: Transition defined for all (state, input) pairs
- Easy to implement: Simple program with state variable
Example: DFA accepting strings ending with "01"
Language: L = {w | w ends with 01}
States: q₀ (start), q₁ (saw 0), q₂ (saw 01 - final)
Alphabet: {0, 1}
Transition Table:
Current | Input 0 | Input 1
--------|---------|--------
→ q₀ | q₁ | q₀
q₁ | q₁ | q₂
q₂✓ | q₁ | q₀
Example traces:
"101" → q₀ →1→ q₀ →0→ q₁ →1→ q₂ ✓ ACCEPT
"110" → q₀ →1→ q₀ →1→ q₀ →0→ q₁ ✗ REJECT
How DFA Works:
- Start in initial state q₀
- Read input symbols one by one from left to right
- For each symbol, follow the transition to next state
- After reading entire input:
- If in final state → ACCEPT
- If not in final state → REJECT
5. Non-Deterministic Finite Automata (NDFA/NFA)
A Non-deterministic Finite Automaton (NFA) is a finite state machine where for each state and input symbol, there can be zero, one, or multiple possible next states.
Formal Definition of NFA:
An NFA is a 5-tuple M = (Q, Σ, δ, q₀, F) where:
- Q: Finite set of states
- Σ: Finite input alphabet
- δ: Q × (Σ ∪ {ε}) → P(Q): Transition function returning SET of states
- q₀ ∈ Q: Initial state
- F ⊆ Q: Set of final states
Key Characteristics of NFA:
- Non-deterministic: Multiple possible transitions for same input
- ε-transitions allowed: Can move without consuming input
- Parallel computation: Machine can be in multiple states simultaneously
- Easier to design: More flexible for complex languages
Example: NFA accepting strings containing "01"
States: q₀ (start), q₁ (saw 0), q₂ (saw 01 - final)
Transitions:
q₀: on 0 → {q₀, q₁} (stay OR move)
on 1 → {q₀}
q₁: on 1 → {q₂}
q₂: on 0,1 → {q₂} (stay in final)
Example: Input "101"
Step 1: q₀ --1--> {q₀}
Step 2: q₀ --0--> {q₀, q₁} (non-deterministic!)
Step 3:
Path 1: q₀ --1--> {q₀} ✗
Path 2: q₁ --1--> {q₂} ✓ ACCEPT
String is accepted if ANY path leads to final state!
NFA vs DFA:
| Feature | DFA | NFA |
|---|---|---|
| Transitions | Exactly one per (state, input) | Zero, one, or many |
| ε-transitions | Not allowed | Allowed |
| Computation | Single path | Multiple parallel paths |
| Design | More complex | Easier, more intuitive |
| Implementation | Faster execution | Slower (backtracking needed) |
| States | May need more states | Usually fewer states |
6. Equivalence of DFA and NDFA
Key Theorem:
For every NFA, there exists an equivalent DFA that accepts the same language. This means NFA and DFA have equal computational power.
Although NFAs can have multiple transitions and ε-moves, they don't recognize any languages that DFAs cannot. We can always convert an NFA to an equivalent DFA.
Subset Construction Algorithm:
Process to convert NFA to DFA:
- ε-closure: Find all states reachable via ε-transitions
- ε-closure(q) = {q} ∪ all states reachable from q via ε only
- DFA states: Each DFA state represents a subset of NFA states
- DFA Q' = P(Q) (power set of NFA states)
- Start state: DFA start = ε-closure(NFA start)
- Transitions: For each DFA state S and input a:
- Find all NFA states reachable from any state in S on input a
- Take ε-closure of that set
- Final states: Any DFA state containing at least one NFA final state
Example: Converting NFA to DFA
NFA:
States: {q₀, q₁, q₂}
Start: q₀
Final: {q₂}
Transitions:
q₀: a → {q₀, q₁}, b → {q₀}
q₁: b → {q₂}
q₂: a,b → ∅
Equivalent DFA:
DFA States (subsets of NFA states):
{q₀} - start
{q₀, q₁}
{q₀, q₂} - final (contains q₂)
Transitions:
{q₀}: a → {q₀, q₁}, b → {q₀}
{q₀,q₁}: a → {q₀, q₁}, b → {q₀, q₂}
{q₀,q₂}: a → {q₀, q₁}, b → {q₀}
Important Points:
- DFA may have exponentially more states than NFA (2^n states possible)
- But many of these states may be unreachable and can be eliminated
- NFA is conceptually simpler, DFA is computationally more efficient
- Both recognize exactly the same class of languages (Regular Languages)
7. Mealy Machine
A Mealy Machine is a type of finite state transducer where the output depends on both the current state AND the current input.
Formal Definition:
Mealy Machine M = (Q, Σ, Δ, δ, λ, q₀) where:
- Q: Finite set of states
- Σ: Input alphabet
- Δ: Output alphabet
- δ: Q × Σ → Q: State transition function
- λ: Q × Σ → Δ: Output function (depends on state AND input)
- q₀: Initial state
Key Features:
- Output is associated with transitions (edges)
- Output produced while making state transition
- Generally requires fewer states than Moore machine
- Responds immediately to input changes (no delay)
- Output length = input length
Example: Mealy Machine - Binary to Gray Code Converter
| State | Input: 0 | Output | Input: 1 | Output |
|---|---|---|---|---|
| q₀ | q₀ | 0 | q₁ | 1 |
| q₁ | q₀ | 1 | q₁ | 0 |
Working: Input "1011" produces output "1110"
8. Moore Machine
A Moore Machine is a finite state transducer where the output depends ONLY on the current state.
Formal Definition:
Moore Machine M = (Q, Σ, Δ, δ, λ, q₀) where:
- Q: Finite set of states
- Σ: Input alphabet
- Δ: Output alphabet
- δ: Q × Σ → Q: State transition function
- λ: Q → Δ: Output function (depends ONLY on state)
- q₀: Initial state
Key Features:
- Output is associated with states (nodes)
- Output produced when entering a state
- May require more states than Mealy machine
- One clock cycle delay in output
- Easier to design and understand
- Output length = input length + 1 (includes initial state output)
Mealy vs Moore Comparison:
| Feature | Mealy Machine | Moore Machine |
|---|---|---|
| Output depends on | State + Input | Only State |
| Output location | On transitions | On states |
| Number of states | Generally fewer | May need more |
| Response time | Immediate | One cycle delay |
| Design complexity | More complex | Simpler |
| Output length | = Input length | = Input length + 1 |
Conversion:
Any Mealy machine can be converted to equivalent Moore machine and vice versa. They have equal computational power.
9. Minimization of Finite Automata
Minimization is the process of reducing the number of states in a DFA while keeping the language accepted unchanged. The goal is to find the DFA with minimum states.
Why Minimize?
- Reduce memory requirements
- Faster execution
- Simpler implementation
- Every DFA has a unique minimal equivalent DFA
Steps for DFA Minimization:
- Step 1: Remove Unreachable States
- States that cannot be reached from start state
- Use BFS/DFS from start state to find reachable states
- Step 2: Remove Dead States
- States from which no final state can be reached
- Do reverse BFS from final states
- Step 3: Merge Equivalent States
- Two states are equivalent if they behave identically for all inputs
- Use Table-Filling Method or Myhill-Nerode Theorem
Table-Filling Algorithm:
- Create a table of all state pairs (p, q)
- Mark pairs where one is final and other is non-final (distinguishable)
- For unmarked pairs, check if they go to marked pairs on any input
- If yes, mark them as distinguishable
- Repeat until no new pairs are marked
- Unmarked pairs are equivalent - merge them
Myhill-Nerode Theorem:
Two states p and q are equivalent if:
For all strings w ∈ Σ*, δ(p,w) and δ(q,w) are both final or both non-final.
If two states are equivalent, they can be merged into one.
10. Two-Way Finite Automata
A Two-Way Finite Automaton (2FA) can move its read head both left and right on the input tape, unlike standard FA which only moves left to right.
Features:
- Read head can move: Left (L), Right (R), or Stay (S)
- Input has end markers (⊢ at start, ⊣ at end)
- Can read same symbol multiple times
- More powerful in terms of state efficiency
Important Result:
Two-way FA and one-way FA are equivalent in power! Both recognize exactly Regular Languages.
2FA may use fewer states, but recognizes same language class as 1FA.
11. Regular Sets and Regular Expressions
Alphabet:
An alphabet (Σ) is a finite, non-empty set of symbols.
Examples: Σ = {0, 1}, Σ = {a, b, c}, Σ = {A, B, ..., Z}
Words/Strings:
A string is a finite sequence of symbols from alphabet.
- Length |w|: Number of symbols in string w
- Empty string ε: String with no symbols, |ε| = 0
- Σ*: Set of all strings over Σ (including ε)
- Σ⁺: Set of all non-empty strings (Σ* - {ε})
Operations on Languages:
| Operation | Notation | Description | Example |
|---|---|---|---|
| Union | L₁ ∪ L₂ | Strings in L₁ or L₂ | {a,b} ∪ {b,c} = {a,b,c} |
| Concatenation | L₁ · L₂ | String from L₁ followed by L₂ | {a,b}·{c} = {ac,bc} |
| Kleene Star | L* | Zero or more concatenations | {a}* = {ε,a,aa,aaa,...} |
| Plus | L⁺ | One or more concatenations | {a}⁺ = {a,aa,aaa,...} |
| Intersection | L₁ ∩ L₂ | Strings in both L₁ and L₂ | {a,b} ∩ {b,c} = {b} |
| Complement | L̄ or L' | All strings not in L | If Σ={a,b}, {a}' = {ε,b,ab,ba,...} |
Regular Expressions:
Algebraic notation for describing regular languages:
- ∅: Empty set (no strings)
- ε: Empty string
- a: Single symbol from Σ
- r₁ + r₂: Union (r₁ | r₂)
- r₁ · r₂: Concatenation (r₁r₂)
- r*: Kleene star (zero or more)
Regular Expression Examples:
| Regular Expression | Language Description | Examples |
|---|---|---|
| 0*1* | Any number of 0's followed by any number of 1's | ε, 0, 01, 0011, 111 |
| (0+1)* | All binary strings | ε, 0, 1, 01, 10, 101 |
| (0+1)*01 | Strings ending with 01 | 01, 001, 101, 0101 |
| (a+b)*abb | Strings ending with abb | abb, aabb, babb, ababb |
| a*b*c* | All a's, then b's, then c's | abc, aabbcc, ac, bc |
Regular Sets:
A Regular Set or Regular Language is a language that can be:
- Expressed using regular expressions, OR
- Accepted by finite automata (DFA/NFA), OR
- Generated by regular grammars
12. Pumping Lemma for Regular Languages
The Pumping Lemma is a property that all regular languages MUST satisfy. It's primarily used as a tool to prove that certain languages are NOT regular.
Statement of Pumping Lemma:
If L is a regular language, then there exists a constant n (pumping length) such that:
For any string w ∈ L where |w| ≥ n, w can be divided into three parts w = xyz satisfying:
- |y| > 0: y is non-empty
- |xy| ≤ n: xy is within first n symbols
- ∀i ≥ 0, xyⁱz ∈ L: Pumping y any number of times keeps string in L
Why is it called "Pumping" Lemma?
Because we can "pump" (repeat) the middle portion y any number of times (0, 1, 2, 3...) and the resulting string must still be in the language.
How to Use Pumping Lemma to Prove Language is NOT Regular:
- Assume language L is regular
- Let n be the pumping length from pumping lemma
- Choose a string w ∈ L where |w| ≥ n (choose strategically!)
- Consider all possible divisions w = xyz satisfying conditions 1 & 2
- Show that for ANY such division, pumping fails (∃i such that xyⁱz ∉ L)
- Conclude language is NOT regular (contradiction!)
Example 1: L = {0ⁿ1ⁿ | n ≥ 0} is NOT regular
Proof:
- Assume L is regular with pumping length n
- Choose w = 0ⁿ1ⁿ, clearly |w| = 2n ≥ n
- By pumping lemma, w = xyz where:
- |y| > 0
- |xy| ≤ n
- Since |xy| ≤ n, both x and y consist only of 0's (they're in first n symbols)
- So y = 0ᵏ for some k > 0
- Consider i = 2: xy²z = 0ⁿ⁺ᵏ1ⁿ
- This has more 0's than 1's
- Therefore xy²z ∉ L
- Contradiction! Therefore L is NOT regular
Example 2: L = {ww | w ∈ {0,1}*} is NOT regular
Language of strings that are repetition of some string (like 0101, 1111, 010010)
Proof sketch:
- Choose w = 0ⁿ1ⁿ0ⁿ1ⁿ (length 4n)
- By pumping lemma, y is in first n symbols (all 0's)
- Pumping y destroys the ww pattern
- Therefore NOT regular
Common Non-Regular Languages:
- L = {0ⁿ1ⁿ | n ≥ 0} - Equal 0's and 1's
- L = {aᵖ | p is prime} - Prime length strings
- L = {ww | w ∈ Σ*} - String repetitions
- L = {palindromes over {0,1}} - Palindromes
- L = {0ⁿ1ᵐ | n ≠ m} - Unequal counts
13. Closure Properties of Regular Sets
Regular languages are closed under various operations, meaning applying these operations to regular languages always produces a regular language.
Regular Languages are CLOSED under:
| Operation | Definition | Proof Method |
|---|---|---|
| Union | L₁ ∪ L₂ | Construct NFA with ε-transitions to both start states |
| Concatenation | L₁ · L₂ | Connect final states of L₁ to start of L₂ via ε |
| Kleene Star | L* | Add ε-transitions from final to start, new final start |
| Intersection | L₁ ∩ L₂ | Product construction (run both DFAs in parallel) |
| Complement | L̄ | Swap final and non-final states in DFA |
| Difference | L₁ - L₂ | L₁ ∩ L̄₂ (using intersection and complement) |
| Reversal | Lᴿ | Reverse all transitions, swap start and final |
Practical Use:
Closure properties help prove languages are regular without constructing automata:
- If L₁ and L₂ are regular, then L₁ ∪ L₂ is regular
- If we can express a language using closure operations on known regular languages, it must be regular
Applications of Pumping Lemma:
- Primary tool to prove languages are NOT regular
- Used in compiler design to check language properties
- Helps understand limitations of finite automata
- Used in formal language theory research
⚡ Quick Revision (Unit I Cheat Sheet)
Core Definitions
- DFA: M = (Q, Σ, δ, q₀, F), δ: Q × Σ → Q, total and deterministic.
- NFA: M = (Q, Σ, δ, q₀, F), δ: Q × (Σ ∪ {ε}) → P(Q), can branch and use ε-moves.
- Equivalence: ∀ NFA ∃ equivalent DFA (subset construction).
- Regex ≡ NFA ≡ DFA ≡ Regular Grammar: All define Regular Languages.
Subset Construction (NFA → DFA)
- Compute ε-closure of start: S₀ = ε-closure(q₀).
- For each DFA state S ⊆ Q and a ∈ Σ: S' = ε-closure(⋃_{q∈S} δ(q,a)).
- Final DFA states: any S with S ∩ F ≠ ∅.
Minimization (DFA)
- Remove unreachable states.
- Table-filling to split distinguishable states (final vs non-final seed).
- Merge unmarked pairs → minimal DFA (unique up to isomorphism).
Pumping Lemma (Regular)
- For |w| ≥ n: w = xyz with |y| > 0, |xy| ≤ n, and ∀i ≥ 0, xyⁱz ∈ L.
- Use to prove NOT regular (contradiction by pumping).
Mealy vs Moore (Transducers)
- Mealy: Output on transitions, depends on (state,input), fewer states, immediate.
- Moore: Output on states, depends on state only, often more states, 1-step delay.
Closure (Regular)
Closed under union, concat, star, intersection, complement, difference, reversal, homomorphism, inverse homomorphism.