Theory of Computation (AL-601) - Unit 5 Short Notes

UNIT 5: THEORY OF COMPUTATION – EXAM-FOCUSED SHORT NOTES

(Based on RGPV Past Papers: Dec 2025, Dec 2024, May 2023, Nov 2023, Nov 2022, Jun 2025, May 2024)

I. FINITE AUTOMATA & FINITE STATE MACHINES WITH OUTPUTS

1.1 Deterministic Finite Automaton (DFA)

• Formal Definition: A DFA is a 5-tuple $$\displaystyle M = (Q, \Sigma, \delta, q_0, F) $$ where:

  • $Q$: finite set of states

  • $\Sigma$: input alphabet

  • $\delta: Q \times \Sigma \to Q$: transition function

  • $$\displaystyle q_0 \in Q $$: start state

  • $F \subseteq Q$: set of final/accepting states

• Language Acceptance: $$\displaystyle L(M) = \{ w \in \Sigma^* \mid \delta^*(q_0, w) \in F \} $$

• Example: DFA for strings over $\{0,1\}$ starting with 1 and ending with 0:

  States: $$\displaystyle q_0 $$ (start), $$\displaystyle q_1 $$, $$\displaystyle q_2 $$ (final).

  $$\displaystyle \delta(q_0,1)=q_1 $$, $$\displaystyle \delta(q_0,0)=q_0 $$ (dead state $$\displaystyle q_d $$ often added for completeness).

  $$\displaystyle \delta(q_1,0)=q_2 $$, $$\displaystyle \delta(q_1,1)=q_1 $$, $$\displaystyle \delta(q_2,0)=q_2 $$, $$\displaystyle \delta(q_2,1)=q_1 $$.

1.2 Non-deterministic Finite Automaton (NFA)

• Formal Definition: NFA is a 5-tuple $$\displaystyle M = (Q, \Sigma, \delta, q_0, F) $$ where $$\displaystyle \delta: Q \times (\Sigma \cup \{\epsilon\}) \to \mathcal{P}(Q) $$.

• ε-transitions: Allow state changes without consuming input.

• Example: NFA for strings over $\{a,b\}$ containing neither aa nor bb:

  States: $$\displaystyle q_0 $$ (start), $$\displaystyle q_1 $$, $$\displaystyle q_2 $$, $$\displaystyle q_3 $$ (final).

  Transitions: $$\displaystyle \delta(q_0,a)=\{q_1\} $$, $$\displaystyle \delta(q_0,b)=\{q_2\} $$, $$\displaystyle \delta(q_1,b)=\{q_3\} $$, $$\displaystyle \delta(q_2,a)=\{q_3\} $$, $$\displaystyle \delta(q_3,a)=\{q_1\} $$, $$\displaystyle \delta(q_3,b)=\{q_2\} $$.

1.3 NFA to DFA Conversion (Subset Construction)

• Method: Each DFA state is a subset of NFA states.

• ε-closure: For NFA with ε-transitions, compute $\epsilon$-closure($S$) = set of states reachable from $S$ via ε-moves.

• Steps:

  1. Start state: $\epsilon$-closure($$\displaystyle q_0 $$).

  2. For each DFA state $S$ and symbol $a$, new state = $\epsilon$-closure($$\displaystyle \bigcup_{s \in S} \delta(s,a) $$).

  3. Repeat until no new states.

• Example: Convert given ε-NFA to DFA (Dec 2024).

1.4 DFA Minimization

• Table-Filling Algorithm:

  1. Mark all distinguishable pairs $(p,q)$ where one is final and other non-final.

  2. Iteratively mark $(p,q)$ if $\exists a \in \Sigma$ such that $(\delta(p,a), \delta(q,a))$ is marked.

  3. Unmarked pairs are equivalent; merge them.

• Equivalence Partitioning: Group states with identical future behavior.

1.5 Finite State Machines with Outputs

• Example: Residue modulo 3 (binary input).

  Moore: States $$\displaystyle q_0 $$ (output 0), $$\displaystyle q_1 $$ (1), $$\displaystyle q_2 $$ (2).

  $$\displaystyle \delta(q_0,0)=q_0 $$, $$\displaystyle \delta(q_0,1)=q_1 $$, etc.

  Mealy: Output on transition = new state’s residue.

1.6 Two-way Finite Automata (2-DFA)

• Definition: Head can move left (L) or right (R) on tape.

• Equivalence: 2-DFA accepts exactly regular languages (same as 1-DFA).

• Key Difference: More expressive description but no extra computational power.

[!TIP]

• Common Pitfall: Forgetting ε-closure in ε-NFA to DFA conversion.

• Exam Focus: Minimization (table-filling), Mealy↔Moore conversion steps, 2-DFA equivalence proof sketch.

II. REGULAR LANGUAGES & EXPRESSIONS

2.1 Regular Expressions (RE)

• Operators: Union ($+$ or $\cup$), concatenation, Kleene star ($$\displaystyle ^* $$).

• Examples:

  • Strings ending with "ab": $$\displaystyle (0+1)^*ab $$

  • Exactly two a’s over $\{a,b\}$: $$\displaystyle b^*ab^*ab^* $$

  • Length divisible by 3 or 5: Complex; use union of $$\displaystyle (aaa)^* $$ and $$\displaystyle (aaaaa)^* $$ with overlaps.

  • $$\displaystyle (0+1)^*(00+11)(0+1)^* $$: Strings containing 00 or 11 as substring.

2.2 Equivalence: FA ↔ RE

• RE → FA (Thompson’s Construction):

  • Build ε-NFA with:

    • For $a$: two states with $a$ transition.

    • For $$\displaystyle R_1 + R_2 $$: new start with ε to each sub-NFA start, new final from each sub-NFA final.

    • For $$\displaystyle R_1 R_2 $$: connect final of $$\displaystyle R_1 $$ to start of $$\displaystyle R_2 $$ via ε.

    • For $$\displaystyle R^* $$: new start/final, ε loops from new final to new start and to $R$ start.

• FA → RE (State Elimination):

  1. Add new start/final states with ε-transitions.

  2. Eliminate states one by one, replacing paths via state $$\displaystyle q_i $$ with direct RE edges.

  3. Final RE = label from new start to new final.

2.3 Arden’s Theorem

• Statement: For regular language $L$ with alphabet $\Sigma$, if $R$ and $S$ are REs such that $L(R) \subseteq L(S)$, then the solution to $$\displaystyle X = RX + S $$ is $$\displaystyle X = R^*S $$.

• Application: Solve system of equations from FA state transitions.

• Example: FA with equations:

  $$\displaystyle A = 0B + 1 $$, $$\displaystyle B = 0A + \epsilon $$

  Solve: $$\displaystyle B = 0(0B+1) + \epsilon = 00B + 0 + \epsilon = 00B + 0^* $$

  $$\displaystyle \Rightarrow B = (00)^*0^* $$

  $$\displaystyle \Rightarrow A = 0(00)^*0^* + 1 $$

2.4 Closure Properties of Regular Languages

[!TIP]

• Key Formula: For intersection, use $$\displaystyle L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}} $$.

• Pumping Lemma: If $L$ regular, $$\displaystyle \exists p>0 $$ such that $\forall w \in L$ with $|w| \ge p$, $$\displaystyle w=xyz $$ with $|xy| \le p$, $$\displaystyle |y|>0 $$, and $\forall i \ge 0$, $$\displaystyle xy^iz \in L $$.

• Non-regular Example: $$\displaystyle L = \{a^n \mid n \text{ prime}\} $$. Assume regular, pump $$\displaystyle y=a^k $$, then $$\displaystyle xy^2z = a^{n+k} $$ not prime for large $n$, contradiction.

III. CONTEXT-FREE GRAMMARS (CFG) & LANGUAGES

3.1 CFG Fundamentals

• Definition: $$\displaystyle G = (V, T, P, S) $$ where $V$ = variables, $T$ = terminals, $P$ = productions, $S$ = start symbol.

• Derivation: $$\displaystyle S \Rightarrow^* w $$ using productions.

• Sentential Form: Any string from $V \cup T$ derivable from $S$.

3.2 Parse Trees & Derivations

• Parse Tree: Hierarchical representation of derivation.

• Leftmost Derivation: Always replace leftmost variable first.

• Rightmost Derivation: Always replace rightmost variable first.

• Example: $S \to aSb \mid ab$, string aabb.

  Leftmost: $S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb$

  Rightmost: $S \Rightarrow aSb \Rightarrow aab b \Rightarrow aabb$ (same tree, not ambiguous).

3.3 Ambiguity in CFG

• Definition: A CFG is ambiguous if some string has >1 parse trees (or leftmost/rightmost derivations differ).

• Classic Example: if-else grammar:

  $S \to if\; S \; else\; S \mid if\; S \mid other$

  String if if else else has two trees.

• Removal Methods:

  1. Redesign grammar (e.g., use matched_stmt and unmatched_stmt).

  2. Left-factoring: $A \to aB \mid aC$ becomes $A \to aD$, $D \to B \mid C$.

3.4 Normal Forms

Chomsky Normal Form (CNF)

• Form: $A \to BC$ or $A \to a$ (allow $S \to \epsilon$ only if $\epsilon \in L(G)$).

• Conversion Steps:

  1. Eliminate $\epsilon$-productions (except possibly $S \to \epsilon$).

  2. Eliminate unit productions ($A \to B$).

  3. Eliminate useless symbols (non-generating or non-reachable).

  4. Convert long productions ($A \to \alpha$ with $|\alpha| \ge 3$) to binary: introduce new variables.

• Example: $S \to AB \mid a$, $A \to a$, $B \to b$ is already in CNF.

Greibach Normal Form (GNF)

• Form: $A \to a\alpha$ where $a \in T$, $$\displaystyle \alpha \in V^* $$ (no $\epsilon$).

• Conversion: Order variables, eliminate left recursion recursively.

• Example: $S \to A B A \mid B S \mid 1$, $B \to S A \mid 0$ (Jun 2025).

3.5 Properties of CFLs

• Closure: Union, concatenation, Kleene star, substitution, reversal.

• Non-closure: Intersection, complement, difference.

  • Example: $$\displaystyle L_1 = \{a^n b^n c^m\} $$, $$\displaystyle L_2 = \{a^m b^n c^n\} $$ are CFLs, but $$\displaystyle L_1 \cap L_2 = \{a^n b^n c^n\} $$ is not CFL.

• Pumping Lemma for CFL: $$\displaystyle \exists p>0 $$ such that $\forall w \in L$ with $|w| \ge p$, $$\displaystyle w=uvxyz $$ with $|vxy| \le p$, $$\displaystyle |vy|>0 $$, and $\forall i \ge 0$, $$\displaystyle uv^ixy^iz \in L $$.

• Non-CFL Example: $$\displaystyle L = \{a^n b^n c^n \mid n \ge 1\} $$. Assume pumping, $$\displaystyle w=a^p b^p c^p $$, pump $vxy$ in first $p$ symbols → imbalance.

3.6 Constructing CFGs

• From RE: Replace + with $\cup$, * with recursion.

  RE: $$\displaystyle (011+1)^*(01)^* $$ →

  $S \to AB$, $A \to 011A \mid 1A \mid \epsilon$, $B \to 01B \mid \epsilon$.

• Specific Languages:

  • $$\displaystyle L = \{w c w^R \mid w \in \{a,b\}^*\} \Rightarrow S \to aSa \mid bSb \mid c $$.

  • $$\displaystyle L = \{a^m b^n c^{2m} d^n \mid m>0, n \ge 0\} \Rightarrow S \to aScc \mid T $$, $T \to bTd \mid \epsilon$.

[!TIP]

• Ambiguity Check: Always try both leftmost and rightmost derivations for the same string.

• CNF Conversion: Eliminate $\epsilon$ first, then unit productions, then binarize.

• GNF: Requires ordering variables; eliminate left recursion by substitution.

IV. PUSHDOWN AUTOMATA (PDA)

4.1 PDA Definition & Model

• Components: $$\displaystyle M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F) $$

  • $\Gamma$: stack alphabet, $$\displaystyle Z_0 $$: initial stack symbol.

• Instantaneous Description (ID): $(q, w, \gamma)$ where $q$ = current state, $w$ = unread input, $\gamma$ = stack top to bottom.

• Transition: $$\displaystyle \delta(q, a, X) \subseteq (Q, \Gamma^*) $$; pop $X$, push string, consume $a$ (or $\epsilon$).

4.2 Deterministic vs Non-deterministic PDA

• DPDA: At most one move for any $(q,a,X)$.

• NPDA: Multiple moves possible.

• Expressive Power: NPDA > DPDA.

  Example: $$\displaystyle L = \{a^n b^n c^n\} $$ is not DPDA-acceptable (requires two counters).

4.3 Acceptance Criteria

4.4 Designing PDA

By Empty Stack (common for CFLs)

• $$\displaystyle L = \{a^n b^n \mid n \ge 1\} $$:

  $$\displaystyle \delta(q_0, a, Z_0) = (q_0, AZ_0) $$

  $$\displaystyle \delta(q_0, a, A) = (q_0, AA) $$

  $$\displaystyle \delta(q_0, b, A) = (q_1, \epsilon) $$

  $$\displaystyle \delta(q_1, b, A) = (q_1, \epsilon) $$

  $$\displaystyle \delta(q_1, \epsilon, Z_0) = (q_1, \epsilon) $$

• $$\displaystyle L = \{a^n b^{3n}\} $$: Push 2 symbols per a, pop 1 per b (adjust counts).

• Even-length palindromes: Non-deterministically guess midpoint, then match.

• $$\displaystyle L = \{w w^R\} $$: Push first half, then pop matching.

• $$\displaystyle L = \{w w^R w\} $$: More complex; store first $w$, then match $$\displaystyle w^R $$, then match $w$ again.

By Final State

• $$\displaystyle L = \{x \mid n_a(x)=n_b(x)\} $$:

  Use stack to track difference: push A for a, pop for b (and vice versa). Accept in a final state when stack empty at end.

4.5 CFG ↔ PDA Conversion

• CFG → PDA (by empty stack):

  • PDA simulates leftmost derivation:

    • Start with $S$ on stack.

    • If top is variable $A$, replace with RHS of some $A \to \alpha$ (push $\alpha$ in reverse).

    • If top is terminal $a$, match with input.

• PDA → CFG:

  • For each pair of states $p,q$ and stack symbol $A$, define variable $[pAq]$ meaning “$A$ generates string that takes PDA from $p$ to $q$ with empty stack”.

  • Productions:

    • $[pAq] \to a[rBs]$ if $\delta(p,a,B) \ni (r,\gamma)$ with $\gamma$ leading from $B$ to $s$ etc.

  • Start variable: $$\displaystyle [q_0 Z_0 q_f] $$ for some $$\displaystyle q_f $$.

[!TIP]

• PDA Design Tip: For languages like $$\displaystyle a^n b^m c^n $$, push for a, pop for c, ignore b.

• Empty Stack vs Final State: Use empty stack for CFLs not deterministic (e.g., palindromes).

• Conversion: CFG→PDA is straightforward; PDA→CFG requires careful variable definition.

V. TURING MACHINES (TM) & COMPUTABILITY

5.1 Turing Machine Definition

• Components: $$\displaystyle M = (Q, \Sigma, \Gamma, \delta, q_0, B, F) $$

  • $\Gamma \supseteq \Sigma \cup \{B\}$ (tape alphabet, $B$ = blank).

  • $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L,R,S\}$.

• Instantaneous Description: $(q, \ldots a \underline{b} \ldots)$ where head on $b$.

5.2 TM Construction Techniques

1. Marking Symbols: Change symbol to mark it (e.g., X for visited a).

2. Shifting Tape: Move block of symbols right/left.

3. Comparing Counts: Use multiple passes or markers.

4. Modular States: Use subroutines (sequences of states).

Examples:

• Even number of 1’s: Toggle state between even/odd on each 1.

• $$\displaystyle L = \{a^n b^n\} $$:

  1. Mark leftmost a as X.

  2. Move right to first unmarked b, mark as Y.

  3. Return left to next unmarked a.

  4. Accept if all a matched with b and no extras.

• $$\displaystyle L = \{a^n b^n c^n\} $$: Extend above: mark a→X, b→Y, c→Z in three passes.

• $$\displaystyle L = \{W C W^R\} $$:

  1. Mark first symbol left of C, remember it.

  2. Move right past C to end, check matching symbol.

  3. Repeat until C reached.

• Multiplication: Repeated addition; use tape for counters.

5.3 Variations of TM

• Multi-tape TM: Multiple tapes with independent heads. Equivalent to single-tape (simulate by interleaving tapes).

• Non-deterministic TM: Multiple transitions; accepts if some path accepts. Equivalent to deterministic TM.

• Multi-track TM: Single tape with multiple tracks (symbols are tuples). Equivalent to standard TM.

5.4 Decidable vs Undecidable

5.5 Halting Problem

• Statement: $$\displaystyle HALT = \{ \langle M,w \rangle \mid M \text{ halts on } w \} $$ is undecidable.

• Proof (Reduction):

  Assume decider $H$ for $HALT$. Construct $D$ that on $\langle M \rangle$:

  • If $H(\langle M,\langle M \rangle \rangle)$ accepts (halts), loop forever.

  • Else halt.

  Then $D(\langle D \rangle)$ contradicts.

5.6 Post Correspondence Problem (PCP)

• Definition: Given pairs $$\displaystyle (x_1,y_1), \dots, (x_k,y_k) $$ over alphabet $\Sigma$, find sequence $$\displaystyle i_1 \dots i_m $$ such that $$\displaystyle x_{i_1} \dots x_{i_m} = y_{i_1} \dots y_{i_m} $$.

• Example: $(0,01), (100,001), (110,10)$ (Nov 2023).

  Try sequences:

  $1: 0 \neq 01$

  $2: 100 \neq 001$

  $1,2: 0100 \neq 01001$

  $2,1: 1000 \neq 00101$

  $1,3: 0110 \neq 011010$

  $3,1: 1100 \neq 1001$

  No solution? Actually check $1,1,3,2$: $$\displaystyle 0\cdot0\cdot110\cdot100 = 001100 $$, $$\displaystyle 01\cdot01\cdot10\cdot001 = 01011001 $$ → no. Often unsolvable.

• Undecidability: Reduce from halting problem.

5.7 Universal Turing Machine (UTM)

• Concept: TM $U$ that simulates any TM $M$ on input $w$ given $\langle M,w \rangle$ as input.

• Importance: Foundation of computability; shows TM can interpret any algorithm.

[!TIP]

• TM Design: Use multiple tracks for multiple counters. Mark and sweep for matching.

• Undecidability Proofs: Use reduction from $HALT$ or $PCP$.

• PCP Example: Always try short sequences first; if no match, likely unsolvable.

VI. ADVANCED TOPICS & COMPLEXITY THEORY

6.1 Chomsky Hierarchy

• Inclusions: Regular $\subset$ CFL $\subset$ CSL $\subset$ RE.

6.2 Complexity Classes

• Reduction: $$\displaystyle L_1 \le_p L_2 $$ means $$\displaystyle L_1 $$ poly-time reducible to $$\displaystyle L_2 $$. If $$\displaystyle L_2 \in P $$, then $$\displaystyle L_1 \in P $$.

6.3 Additional Models

• Petri Nets:

  • Components: Places (circles), transitions (rectangles), tokens (dots).

  • Firing: Transition fires if each input place has ≥1 token; consumes one token from each input, produces one in each output.

  • Applications: Concurrent systems, workflow modeling.

• Linear Bounded Automaton (LBA): TM with tape bounded by input length. Equivalent to context-sensitive grammars.

• Two-way DFA: Already in Section I; equivalent to one-way DFA.

[!TIP]

• Chomsky Hierarchy: Remember Type 0→TM, Type 1→LBA, Type 2→PDA, Type 3→FA.

• NP-Complete: Must show (1) in NP, (2) NP-hard via reduction from known NP-complete problem (e.g., SAT).

• Petri Nets: Focus on reachability and deadlock detection.

VII. FREQUENTLY ASKED CONSTRUCTION & PROOF PROBLEMS

Conversion Problems

Design Problems

• DFA/NFA: For given language specs (e.g., exactly two a’s, no aa/bb).

• PDA: By empty stack for $$\displaystyle a^n b^n $$, $$\displaystyle a^n b^{3n} $$, $$\displaystyle a^n b^m c^n $$, palindromes; by final state for $$\displaystyle n_a=n_b $$.

• TM: Even 1’s, $$\displaystyle a^n b^n c^n $$, $$\displaystyle W C W^R $$, multiple of 3 (binary), multiplication.

Proof Problems

• Non-regular: Pumping lemma (e.g., $$\displaystyle \{a^n \mid n \text{ prime}\} $$).

• Non-CFL: Pumping lemma or closure (e.g., $$\displaystyle \{a^n b^n c^n\} $$ via intersection with regular).

• Undecidability: Halting Problem (diagonalization), PCP (reduce from $HALT$).

• Deterministic CFL: Construct DPDA (e.g., $$\displaystyle a^n b^n $$).

VIII. KEY THEOREMS & CONCEPTS (SHORT NOTE PRIORITIES)

1. Arden’s Theorem: Solution to $$\displaystyle X = RX + S $$ is $$\displaystyle R^*S $$. Used to derive RE from FA equations.

2. Pumping Lemma (Regular): $\exists p$ such that $$\displaystyle w=xyz $$, $|xy|\le p$, $$\displaystyle |y|>0 $$, $$\displaystyle xy^iz \in L $$ for all $i$. Proves non-regularity.

3. Pumping Lemma (CFL): $$\displaystyle w=uvxyz $$, $|vxy|\le p$, $$\displaystyle |vy|>0 $$, $$\displaystyle uv^ixy^iz \in L $$. Proves non-CFL.

4. Closure Properties: Regular: all basic ops; CFL: union, concat, star only.

5. CNF & GNF: CNF: $A\to BC$ or $a$; GNF: $A\to a\alpha$. Conversion steps critical.

6. PDA Acceptance: Final state vs empty stack; equivalent for NPDA, not for DPDA.

7. Halting Problem: Undecidable; no TM decides $$\displaystyle HALT = \{ \langle M,w \rangle \mid M \text{ halts on } w \} $$.

8. Complexity Classes:

   • P: Poly-time deterministic.

   • NP: Poly-time non-deterministic/verifiable.

   • NP-Complete: In NP + NP-hard (e.g., SAT).

   • NP-Hard: At least as hard as NP (may be undecidable).

9. Universal TM: Simulates any TM; basis of computability.

10. PCP: Given pairs $$\displaystyle (x_i,y_i) $$, find sequence with equal concatenation. Undecidable.

11. Petri Nets: Graph model for concurrent systems; places, transitions, tokens.

12. Two-way DFA: Head moves L/R; accepts exactly regular languages.

13. CFG Properties: Ambiguity, useless symbols, left recursion, generative/recursive.

[!TIP]

• Exam Focus: Arden’s theorem (solve equations), pumping lemma (write $$\displaystyle w=xyz $$ properly), CNF conversion (step-by-step), Halting Problem (reduction sketch), NP-completeness (reduction from SAT).

• Common Pitfalls:

• Confusing Mealy output (transition) vs Moore (state).

• Forgetting to eliminate ε-productions before CNF.

• Misapplying pumping lemma (choose $w$ based on $p$).

• Assuming CFLs closed under intersection/complement.

Diagrams Reference:

• For state diagrams (DFA/NFA/Mealy/Moore), use

  DiagramCANVAS: Draw circles for states, arrows for transitions, label with input/output
  .

• For parse trees:

  DiagramCANVAS: Root S, branches to terminals/variables, left-to-right order
  .

• For TM tape:

  DiagramCANVAS: Semi-infinite tape left/right, head position marked, symbols
  .

Final Note: Practice conversions and designs from past papers—they form 70% of questions. Memorize key definitions (e.g., DFA 5-tuple, PDA acceptance modes) and theorems (Arden’s, pumping lemmas).