Theory of Computation (IT-503 (A)) - Unit 4 Short Notes

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

I. FINITE AUTOMATA & REGULAR LANGUAGES

Deterministic Finite Automata (DFA)

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

  • $Q$: Finite set of states.

  • $\Sigma$: Finite input alphabet.

  • $$\displaystyle \delta: Q \times \Sigma \rightarrow Q $$: Transition function.

  • $$\displaystyle q_0 \in Q $$: Start state.

  • $F \subseteq Q$: Set of final (accepting) states.

• Language Acceptance: A string $w$ is accepted if the machine halts in a state from $F$ after processing $w$.

• State Diagram: Circles for states, arrows for transitions, double circle for final states.

• Transition Table: Rows = states, columns = input symbols, entries = next state.

• Common Patterns:

  • Strings starting with 1 and ending with 0 over $\{0,1\}$.

  • Strings with exactly two a's and two b's over $\{a,b\}$.

  • Detecting subsequence 1100 with overlap.

Non-deterministic Finite Automata (NFA)

• Formal Definition: $$\displaystyle M = (Q, \Sigma, \delta, q_0, F) $$ where $$\displaystyle \delta: Q \times \Sigma \rightarrow P(Q) $$ (power set of $Q$).

• ε-Transition (ε-NFA): Transition without consuming input: $$\displaystyle \delta: Q \times (\Sigma \cup \{\epsilon\}) \rightarrow P(Q) $$.

• Acceptance: A string is accepted if some computation path ends in a final state.

• Key Difference from DFA: Multiple next states possible for a single state-symbol pair; ε-moves allowed.

Equivalence & Conversion

• Equivalence: DFA, NFA, and ε-NFA recognize the same class of languages (Regular Languages).

• Subset Construction (NFA/ε-NFA → DFA):

  1. States: All subsets of $Q$ (powerset).

  2. Start state: $\epsilon$-closure of $$\displaystyle \{q_0\} $$.

  3. Transition: For DFA state $S$ and symbol $a$, new state = $\epsilon$-closure of $$\displaystyle \bigcup_{q \in S} \delta(q,a) $$.

  4. Final states: Any DFA state containing at least one NFA final state.

• ε-Closure: Set of states reachable from a state via only ε-transitions (including itself).

• Frequent Exam Task: Convert given NFA/ε-NFA to equivalent DFA.

Minimization of DFA

• Goal: Remove equivalent (indistinguishable) states.

• Table-Filling Method:

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

  2. Iteratively mark $(p,q)$ if for some $a \in \Sigma$, $(\delta(p,a), \delta(q,a))$ is already marked.

  3. Unmarked pairs are equivalent; merge them.

• Myhill-Nerode Theorem: Provides necessary and sufficient condition for minimality.

• Frequent Exam Task: Minimize given DFA.

Finite Automata with Outputs

• Applications: Sequence detectors, residue calculators (mod 3, 5).

• Frequent Exam Tasks: Differentiate, convert Mealy ↔ Moore.

Regular Expressions (RE)

• Operators: Union ($+$ or $\cup$), Concatenation, Kleene Star ($$\displaystyle ^* $$). Precedence: Star > Concatenation > Union.

• Constructing RE: For language specification (e.g., strings ending with "ab" → (a+b)*ab).

• From Automaton → RE (State Elimination):

  1. Ensure single start and final state (add new ones if needed).

  2. Eliminate states one by one, updating edge labels with REs.

  3. Final RE = label on direct edge from new start to new final.

• Arden's Theorem:

  • Statement: For $R$ and $S$ being regular expressions over $\Sigma$, if $R$ does not contain $\epsilon$, the equation $$\displaystyle X = R \cdot X + S $$ has a unique solution $$\displaystyle X = R^* S $$.

  • Application: Solve system of linear equations derived from automaton's state equations.

  • Frequent Exam Tasks: Explain theorem, construct RE using it.

Closure Properties of Regular Languages

Regular languages are closed under:

• Union: $$\displaystyle L_1 \cup L_2 $$

• Intersection: $$\displaystyle L_1 \cap L_2 $$ (via product automaton)

• Complement: $\overline{L}$ (swap final/non-final states in complete DFA)

• Concatenation: $$\displaystyle L_1 \cdot L_2 $$

• Kleene Star: $$\displaystyle L^* $$

• Reversal: $$\displaystyle L^R $$

• Homomorphism & Inverse Homomorphism

• Frequent Exam Task: Define and explain key properties.

Pumping Lemma for Regular Languages

• Statement: If $L$ is regular, $\exists$ a pumping length $p \geq 1$ such that $\forall w \in L$ with $|w| \geq p$, $w$ can be written as $$\displaystyle w = xyz $$ satisfying:

  1. $$\displaystyle |y| > 0 $$

  2. $|xy| \leq p$

  3. $$\displaystyle \forall i \geq 0,\; xy^iz \in L $$

• Use: To prove a language is non-regular by contradiction. Assume $L$ regular, choose $w$, show no valid split exists.

• Example: Prove $$\displaystyle L = \{a^n \mid n \text{ is prime}\} $$ is not regular.

• Frequent Exam Task: Apply pumping lemma.

Decision Algorithms

• Emptiness: Check if any state reachable from $$\displaystyle q_0 $$ is final (via BFS/DFS).

• Finiteness: Minimize DFA; check for cycles reachable from start and leading to final.

• Membership: Simulate DFA on input.

• Equivalence: Minimize both DFAs; check isomorphism.

Two-way Finite Automata (2-DFA)

• Model: Like DFA but head can move Left or Right on tape.

• Power: Equivalent in power to standard DFA (recognizes same class: regular languages), but may require fewer states.

• Frequent as Short Note.

II. CONTEXT-FREE GRAMMARS & LANGUAGES (CFG)

Context-Free Grammar (CFG)

• Formal Definition: $$\displaystyle G = (V, T, P, S) $$ where:

  • $V$: Set of non-terminals (variables).

  • $T$: Set of terminals (alphabet).

  • $P$: Set of productions of form $$\displaystyle A \rightarrow \alpha $$, $A \in V$, $$\displaystyle \alpha \in (V \cup T)^* $$.

  • $S \in V$: Start symbol.

• Derivation: Applying productions to replace a non-terminal. Types:

  • Leftmost: Always replace leftmost non-terminal.

  • Rightmost: Always replace rightmost non-terminal.

• Frequent Exam Task: Derive a string (e.g., "aabb" from $$\displaystyle S \rightarrow aSb \mid ab $$).

Parse Trees (Derivation Trees)

• Graphical representation of derivation.

• Root: Start symbol $S$.

• Internal nodes: Non-terminals.

• Leaves: Terminals (yield of the tree = string read left-to-right).

• Frequent Exam Task: Draw parse tree for given string and grammar.

Ambiguity in CFG

• Definition: A CFG is ambiguous if there exists at least one string in its language that has more than one distinct parse tree (or equivalently, more than one leftmost/rightmost derivation).

• Example Ambiguous Grammar (from papers):

  
  S → aAB
  
  A → bC / cd
  
  B → c / d
  
  C → cd
  
  

  String "acd" can be derived via S→aAB→aA d→a cd (using A→cd) or S→aAB→aAB→aA d→a cd (using B→d then A→cd? Need check).

• Frequent Exam Task: Check given grammar for ambiguity, show two leftmost derivations/parse trees.

Methods to Remove Ambiguity

• Left-factoring: Factor common prefixes.

  • $$\displaystyle A \rightarrow \alpha\beta_1 \mid \alpha\beta_2 $$ becomes $$\displaystyle A \rightarrow \alpha A' $$, $$\displaystyle A' \rightarrow \beta_1 \mid \beta_2 $$.

• Introduce new non-terminals to enforce a unique grouping.

• Frequent Exam Task: Explain methods, convert ambiguous grammar to unambiguous.

Normal Forms for CFG

• Chomsky Normal Form (CNF):

  • Every production is of form:

    • $$\displaystyle A \rightarrow BC $$ (two non-terminals)

    • $$\displaystyle A \rightarrow a $$ (one terminal)

    • $$\displaystyle S \rightarrow \epsilon $$ (only if $\epsilon \in L(G)$).

  • Conversion Steps:

    1. Remove ε-productions (except possibly $$\displaystyle S \rightarrow \epsilon $$).

    2. Remove unit productions ($$\displaystyle A \rightarrow B $$).

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

    4. Convert remaining productions to $$\displaystyle A \rightarrow BC $$ or $$\displaystyle A \rightarrow a $$ (break long RHS, introduce new non-terminals for terminals).

  • Frequent Exam Task: Convert given CFG to CNF step-by-step.

• Greibach Normal Form (GNF):

  • Every production is of form $$\displaystyle A \rightarrow a\alpha $$, where $a \in T$, $$\displaystyle \alpha \in V^* $$ (terminal followed by zero or more non-terminals).

  • Conversion: Often done by first converting to CNF, then applying specific transformations to ensure terminal first.

  • Frequent Exam Task: Convert CFG to GNF, discuss both CNF & GNF with examples.

Properties of Context-Free Languages (CFL)

• Closure: Closed under union, concatenation, Kleene star. NOT closed under intersection or complement.

• Pumping Lemma for CFL:

  • If $L$ is CFL, $$\displaystyle \exists p > 0 $$ such that $\forall w \in L$ with $|w| \geq p$, $$\displaystyle w = uvxyz $$ with:

    1. $$\displaystyle |vy| > 0 $$

    2. $|vxy| \leq p$

    3. $$\displaystyle \forall i \geq 0,\; uv^ixy^iz \in L $$

  • Use to prove non-CFL (e.g., $$\displaystyle L = \{a^n b^n c^n \mid n \geq 1\} $$).

• Relationship: Every regular language is CFL, but not vice-versa (e.g., $$\displaystyle \{a^n b^n\} $$ is CFL but not regular).

• Frequent Exam Task: Show language is not CFL using pumping lemma or closure (intersection with regular).

Differentiation: CFG vs. CSG

• Frequent Exam Task: Differentiate CFG and CSG.

III. PUSHDOWN AUTOMATA (PDA)

Definition and Model

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

  • $Q$: Finite states.

  • $\Sigma$: Input alphabet.

  • $\Gamma$: Stack alphabet ($\Gamma \supseteq \Sigma$ often).

  • $$\displaystyle \delta: Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma \rightarrow P(Q \times \Gamma^*) $$: Transition function.

  • $$\displaystyle q_0 $$: Start state.

  • $$\displaystyle Z_0 $$: Initial stack symbol.

  • $F \subseteq Q$: Final states (if accepting by final state).

• Components: Finite control, input tape (read-only, left-to-right), stack (LIFO).

• Frequent Exam Task: Explain model with sketch.

Instantaneous Description (ID)

• Representation: $(q, w, \gamma)$

  • $q$: current state.

  • $w$: unread input (remaining suffix).

  • $\gamma$: stack contents (top symbol first).

• Transition: $(q, a w, X \gamma) \vdash (p, w, \beta \gamma)$ if $(p, \beta) \in \delta(q, a, X)$.

• Frequent Exam Task: Explain ID.

Acceptance Criteria

1. By Final State: $w$ accepted if $\exists$ computation ending in state $q \in F$ with empty or any stack.

2. By Empty Stack: $w$ accepted if $\exists$ computation ending with empty stack (any state).

• Equivalence: For any PDA accepting by one mode, an equivalent PDA can be constructed for the other mode.

Deterministic vs. Non-deterministic PDA (DPDA vs. NPDA)

• Frequent Exam Task: Define DPDA, differentiate from NPDA.

Designing PDAs

• Strategy: Use stack to match symbols or count differences.

  • For $$\displaystyle a^n b^n $$: Push a's, pop for each b.

  • For $$\displaystyle a^n b^m c^n $$: Push a's, ignore b's, pop for c's.

  • For palindromes $$\displaystyle ww^R $$: Push first half, guess midpoint (ε-move), then pop and match.

• Common Languages from Papers:

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

  • $$\displaystyle L = \{0^n 1^n \mid n \geq 0\} $$

  • $$\displaystyle L = \{ww^R \mid w \in \{a,b\}^*\} $$ (even-length palindromes)

  • $$\displaystyle L = \{a^n b^m c^n \mid n,m \geq 1\} $$

  • $$\displaystyle L = \{a^n b^{3n} \mid n \geq 0\} $$

  • $$\displaystyle L = \{w \mid w \text{ starts and ends with same symbol over } \{0,1\}\} $$

• Frequent Exam Task: Design NPDA/DPDA for given language.

CFG ↔ PDA Equivalence

• CFG → PDA (by empty stack):

  1. PDA simulates leftmost derivation.

  2. Stack holds current sentential form (top = leftmost symbol).

  3. For production $$\displaystyle A \rightarrow \gamma $$, add transition: $$\displaystyle (q, \epsilon, A) \rightarrow (q, \gamma) $$.

  4. For each terminal $a$, add: $$\displaystyle (q, a, a) \rightarrow (q, \epsilon) $$.

  5. Start with $S$ on stack. Accept by empty stack.

• PDA → CFG:

  • For each PDA transition $$\displaystyle (p, a, A) \rightarrow (q, \beta) $$, create production $$\displaystyle A_p \rightarrow a q_\beta $$ where $$\displaystyle q_\beta $$ encodes state $q$ and string $\beta$.

  • Standard construction yields CFG generating strings that take PDA from start to empty stack.

• Frequent Exam Tasks: Convert CFG to PDA, convert PDA to CFG.

Closure Properties of CFL (via PDA)

• Closed: Union, concatenation, Kleene star (constructible by combining PDAs).

• Not Closed: Intersection, complement ( PDA's stack is single LIFO; cannot handle two independent counts like $$\displaystyle a^n b^n c^n $$).

IV. TURING MACHINES & DECIDABILITY

Turing Machine (TM) Model

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

  • $Q$: Finite states.

  • $\Sigma$: Input alphabet ($\epsilon \notin \Sigma$).

  • $\Gamma$: Tape alphabet ($\Sigma \subset \Gamma$, $B \in \Gamma$ is blank).

  • $$\displaystyle \delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\} $$: Transition function.

  • $$\displaystyle q_0 $$: Start state.

  • $B$: Blank symbol.

  • $F \subseteq Q$: Final states.

• Tape: Semi-infinite (left-end marked), read/write head moves Left/Right.

• Frequent Exam Task: Explain model and construction techniques.

TM as Language Acceptor/Enumerator

• Acceptance by Final State: $w$ accepted if TM enters $q \in F$ and halts.

• Acceptance by Halting: TM halts (in any state) on $w$.

• Language Classes:

  • Turing Recognizable (Recursively Enumerable, RE): TM halts and accepts strings in $L$; may loop forever on $w \notin L$.

  • Turing Decidable (Recursive): TM always halts (accepts or rejects). Recursive languages are a proper subset of RE.

• Frequent Exam Task: Explain decidable, undecidable, recursive, RE languages.

Techniques for TM Construction

• Storing/Matching Symbols: Mark matched symbols (e.g., change a to X, b to Y).

• Counting: Use multiple tracks or multiple tapes to simulate counters.

• Common Languages from Papers:

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

  • $$\displaystyle L = \{0^n 1^{2n} \mid n \geq 0\} $$

  • $$\displaystyle L = \{0^n 1^{2n} 2^n \mid n \geq 0\} $$

  • $$\displaystyle L = \{W C W^R \mid W \in \{0,1\}^*\} $$

  • $$\displaystyle L = \{W \mid W \text{ is multiple of 3 over } \{0,1\}\} $$

  • $$\displaystyle L = \{a^n b^n c^n \mid n \geq 1\} $$

  • Multiplication of two unary numbers on tape.

• Frequent Exam Task: Design TM for given language.

Variants of TM

• Multi-tape TM: Equivalent to single-tape (can simulate with tracks).

• Non-deterministic TM: Equivalent to deterministic (can simulate via dovetailing).

• Universal Turing Machine (UTM):

  • A TM that takes as input description of another TM $M$ and input $w$, and simulates $M$ on $w$.

  • Significance: Foundation of stored-program computers; shows existence of a "universal" machine.

• Frequent as Short Note: UTM.

Undecidable Problems

• Halting Problem (HP):

  • Definition: $$\displaystyle HALT_{TM} = \{\langle M, w \rangle \mid M \text{ halts on input } w\} $$.

  • Undecidability: No TM decides $$\displaystyle HALT_{TM} $$. Proof by diagonalization or reduction from self-halting problem.

  • Frequent Exam Task: State and prove HP is undecidable.

• Post Correspondence Problem (PCP):

  • Definition: Given two lists $$\displaystyle X = (x_1, ..., x_k) $$ and $$\displaystyle Y = (y_1, ..., y_k) $$ of strings over $\Sigma$, does there exist a sequence of indices $$\displaystyle i_1, i_2, ..., i_m $$ such that $$\displaystyle x_{i_1} x_{i_2} ... x_{i_m} = y_{i_1} y_{i_2} ... y_{i_m} $$?

  • Solving: Find concatenation that matches.

  • Example from papers: $$\displaystyle X = (\text{ba, ab, ba, baa, b}) $$, $$\displaystyle Y = (\text{bab, baa, ba, a, aba}) $$. Solution: indices (1,2,1,4,5) → baabbaaaba = babbaaaba? Check.

  • Frequent Exam Task: Define PCP, solve given instance, check existence.

• Other Undecidable Problems: "Does TM $M$ halt on input 101?" (reduction from HP).

• Frequent as Short Note: Undecidable problem (general).

Reducibility & Rice's Theorem

• Many-one Reduction ($$\displaystyle \leq_m $$): $$\displaystyle A \leq_m B $$ means there is computable function $f$ such that $x \in A \iff f(x) \in B$.

• Rice's Theorem: Any non-trivial property of RE languages is undecidable. (Non-trivial = not true for all RE languages, nor false for all).

  • Example: "Is $L(M)$ finite?" is undecidable.

• Used implicitly in undecidability proofs.

V. COMPLEXITY THEORY

Complexity Classes

• P (Polynomial Time):

  • Problems solvable by a deterministic TM in time $$\displaystyle O(n^k) $$ for some constant $k$.

  • Examples: Sorting, shortest path, membership in regular languages.

• NP (Non-deterministic Polynomial Time):

  • Problems verifiable in polynomial time (given a certificate).

  • Equivalently, solvable by a non-deterministic TM in polynomial time.

  • Examples: SAT, Hamiltonian cycle, integer factorization.

• Relationship: $P \subseteq NP$. $$\displaystyle P = NP $$? (Open problem).

• Frequent Exam Task: Explain P and NP with examples.

NP-Complete Problems

• Definition: A problem $L$ is NP-complete if:

  1. $L \in NP$.

  2. Every problem in $A \in NP$ is polynomial-time reducible to $L$ ($$\displaystyle A \leq_p L $$).

• Significance: "Hardest" problems in NP. If any NP-complete problem is in P, then $$\displaystyle P = NP $$.

• Examples: SAT (Cook-Levin Theorem), 3-SAT, Clique, Vertex Cover, Traveling Salesman (decision version).

• Frequent Exam Task: Explain NP-complete with example (e.g., SAT).

NP-Hard Problems

• Definition: A problem $L$ is NP-hard if every problem in NP is polynomial-time reducible to $L$.

• May not be in NP (e.g., undecidable problems like Halting Problem are NP-hard).

• Examples: Halting Problem (undecidable, hence NP-hard), optimization versions of NP-complete problems (e.g., "find shortest TSP tour").

• Frequent as Short Note: NP-Hard.

Chomsky Hierarchy (Recap)

• Frequent as Short Note: Chomsky hierarchy.

VI. ADVANCED & MISCELLANEOUS TOPICS (Short Notes)

Petri Nets Model

• Components:

  • Places (circles): Represent conditions/state.

  • Transitions (rectangles/boxes): Represent events.

  • Tokens (dots): Represent resources/state.

  • Arcs: Directed edges from places to transitions or transitions to places.

• Bipartite Graph: Places and transitions form two disjoint sets; arcs only between different types.

• Firing Rule: A transition fires if each input place has at least one token. Firing removes one token from each input place and adds one token to each output place.

• Applications: Modeling concurrent, asynchronous, and distributed systems (e.g., communication protocols, workflow).

• Frequent as Short Note.

Composite Machines

• Concept: Constructing a new automaton from two or more existing automata to recognize combined language operations.

• Product Construction: For intersection of regular languages: $$\displaystyle M = M_1 \times M_2 $$ with states $$\displaystyle (q_1, q_2) $$, start $$\displaystyle (q_{01}, q_{02}) $$, final states $$\displaystyle \{(q_1, q_2) \mid q_1 \in F_1 \land q_2 \in F_2\} $$.

• Frequent Exam Task: Explain with example.

Regular Grammars

• Right-linear Grammar: Productions of form $$\displaystyle A \rightarrow aB $$ or $$\displaystyle A \rightarrow a $$ (or $$\displaystyle A \rightarrow \epsilon $$), where $A,B \in V$, $a \in T$.

• Left-linear Grammar: Productions of form $$\displaystyle A \rightarrow Ba $$ or $$\displaystyle A \rightarrow a $$.

• Equivalence: Right-linear grammars generate exactly the regular languages; equivalent to DFAs/NFAs.

• Frequent Exam Task: Find regular grammar for given language (e.g., "at most one a and more than two b's").

Applications of Automata Theory

• Lexical Analyzers: DFA for token recognition in compilers.

• Pattern Matching: Regular expressions in grep, text editors.

• Protocol Verification: Model communication with finite-state machines.

• Circuit Design: Sequential circuits as finite automata.

Linear Bounded Automaton (LBA)

• Model: TM where tape is limited to region containing input (length linearly bounded by input).

• Power: Equivalent to context-sensitive grammars (Type-1).

• Note: Not directly asked in past papers but part of Chomsky hierarchy.

Closure Properties of Recursive Languages

• Recursive languages are closed under:

  • Union, Intersection, Complement: Can be decided by simulating both TMs and combining results.

  • Concatenation, Kleene Star: Construct decider for combined language.

• Frequent Exam Task: Prove closure under union, intersection, complement.

VII. SYNTHESIS & PROBLEM-SOLVING PATTERNS

Conversion Problems (Very High Frequency)

Design Problems (Very High Frequency)

• Design FA/RE: For language specification (e.g., "strings with substring 00", "divisible by 3").

• Design PDA: For CFLs (use stack for matching/counting). Specify acceptance mode.

• Design TM: For recursively enumerable/decidable languages. Use marking, multiple tracks, simulation of counters.

• Design DPDA: For deterministic CFLs (e.g., $$\displaystyle a^n b^n $$).

Proof Problems

• Non-regularity: Use pumping lemma or closure (intersect with regular to get known non-regular).

• Non-CFL: Use pumping lemma for CFL or closure (intersect with regular to get $$\displaystyle \{a^n b^n c^n\} $$).

• Undecidability: Reduce from Halting Problem or PCP. Show that if problem were decidable, then HP would be decidable (contradiction).

Ambiguity Analysis

1. Find a string with two distinct parse trees (or leftmost derivations).

2. To remove ambiguity: left-factor or introduce new non-terminals to enforce unique grouping.

3. Show unambiguous grammar and derive the same string uniquely.

[!TIP] EXAM STRATEGY

• Conversion Problems (NFA→DFA, CFG→CNF, Mealy→Moore): Follow step-by-step algorithms; partial credit for correct steps.

• Design Problems (PDA, TM): Clearly state strategy (e.g., "use stack to count a's"), then define transitions/states.

• Proofs (Pumping Lemma): State lemma correctly, choose appropriate $w$, consider all splits, show contradiction.

• Undecidability: Reduce from known undecidable problem (HP or PCP). Define computable transformation.

• Short Notes (Petri Nets, UTM, 2-DFA): Define, give components, state significance/applications concisely.

• Common Pitfall: Confusing Mealy (output on transition) vs. Moore (output on state). In conversion, Moore may need extra states.

• Time Management: For 7-mark questions, aim for 1-1.5 pages with clear diagrams/tables.