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

I. Finite Automata and Finite State Machines

Deterministic Finite Automata (DFA)

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

  • \( Q \): finite set of states

  • \( \Sigma \): input alphabet

  • \( \delta: Q \times \Sigma \to Q \): transition function

  • \( q_0 \in Q \): start state

  • \( F \subseteq Q \): set of final (accepting) states

• Language Acceptance: A string \( w \) is accepted if the state reached after processing all symbols is in \( F \).

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

• Examples:

  • Strings over \( \{0,1\} \) starting with 1 and ending with 0:

    States: \( q_0 \) (start), \( q_1 \) (saw 1), \( q_2 \) (saw 1 and ended with 0), dead state \( q_d \).

    Transitions: \( \delta(q_0,1)=q_1 \), \( \delta(q_0,0)=q_d \); \( \delta(q_1,0)=q_2 \), \( \delta(q_1,1)=q_1 \); \( \delta(q_2,0)=q_2 \), \( \delta(q_2,1)=q_d \); all others to \( q_d \). Final: \( q_2 \).

  • Residue modulo \( N \) (binary input): States represent remainders \( 0,1,\dots,N-1 \). Transition: from state \( r \) on bit \( b \), new remainder \( (2r + b) \mod N \). Final state: remainder 0.

Non-deterministic Finite Automata (NFA)

• Definition: \( M = (Q, \Sigma, \delta, q_0, F) \) where \( \delta: Q \times (\Sigma \cup \{\epsilon\}) \to 2^Q \). Multiple transitions or \( \epsilon \)-moves allowed.

• Language Acceptance: \( w \) accepted if exists a path from \( q_0 \) to some \( f \in F \) labeled \( w \).

• Equivalence to DFA: Every NFA has an equivalent DFA via subset construction.

• Example: Strings over \( \{a,b\} \) with neither "aa" nor "bb":

  States: \( q_0 \) (start, no previous symbol), \( q_a \) (last was a), \( q_b \) (last was b), \( q_d \) (dead).

  Transitions: \( \delta(q_0,a)=\{q_a\} \), \( \delta(q_0,b)=\{q_b\} \); \( \delta(q_a,b)=\{q_b\} \), \( \delta(q_a,a)=\{q_d\} \); \( \delta(q_b,a)=\{q_a\} \), \( \delta(q_b,b)=\{q_d\} \); \( q_d \) loops to itself. Final: \( q_0, q_a, q_b \) (all except dead).

Conversion Techniques

• NFA to DFA (Subset Construction):

  • DFA states: subsets of NFA states.

  • Start state: \( \epsilon \)-closure of \( q_0 \).

  • Transition: \( \delta_{DFA}(S, a) = \bigcup_{s \in S} \delta_{NFA}(s, a) \) (including \( \epsilon \)-closure).

• ε-NFA to NFA:

  • Compute \( \epsilon \)-closure for each state.

  • For each state \( S \) and symbol \( a \), \( \delta_{NFA}(S, a) = \epsilon \)-closure of \( \bigcup_{s \in S} \delta_{\epsilon\text{-NFA}}(s, a) \).

• DFA Minimization:

  • Table-filling algorithm: Mark all distinguishable pairs (one final, one not). Iteratively mark \( (p,q) \) if for some \( a \), \( (\delta(p,a), \delta(q,a)) \) is marked. Unmarked pairs are equivalent.

  • Myhill-Nerode theorem: Number of states in minimal DFA = number of equivalence classes under relation \( x \equiv_L y \) iff \( \forall z, xz \in L \Leftrightarrow yz \in L \).

Finite Automata with Outputs

• Mealy Machine: Output on transitions. \( M = (Q, \Sigma, \Delta, \delta, \lambda, q_0) \) where \( \lambda: Q \times \Sigma \to \Delta \).

  • Example: Binary residue mod 5. States: remainders 0–4. Output: current remainder after reading bit. Transition: from \( r \) on \( b \), new \( (2r+b) \mod 5 \), output that remainder.

• Moore Machine: Output on states. \( M = (Q, \Sigma, \Delta, \delta, \lambda, q_0) \) where \( \lambda: Q \to \Delta \).

  • Example: Binary residue mod 3. States: 0,1,2. Output: state value. Transition same as Meley but output is state after transition.

• Conversion:

  • Mealy → Moore: Split states with different outputs on incoming transitions.

  • Moore → Mealy: Assign output of next state to transition.

• Composite Machines:

  • Series: Output of first is input to second.

  • Parallel: Same input to both, outputs combined (e.g., union of languages).

Specialized DFA Constructions

• Exact symbol counts: e.g., exactly two \( a \)'s over \( \{a,b\} \):

  States: \( q_0 \) (0 a's), \( q_1 \) (1 a), \( q_2 \) (2 a's), \( q_3 \) (>2 a's). Transitions: on \( a \) from \( q_i \) to \( q_{i+1} \) for \( i<3 \), stay in \( q_3 \) for \( i=3 \). On \( b \), all states loop. Final: \( q_2 \).

• Pattern avoidance: e.g., no "aa" or "bb" (from NFA example above, convert to DFA via subset construction).

• Start ≠ end: Over \( \{0,1\} \), strings where first and last symbols differ:

  States: \( q_0 \) (start, no symbol yet), \( q_{1,0} \) (started with 0), \( q_{1,1} \) (started with 1), \( q_{end0} \) (last was 0), \( q_{end1} \) (last was 1). Transitions update start on first symbol, end on each symbol. Accept if start symbol ≠ last symbol.

II. Regular Languages and Expressions

Regular Expressions

• Operators: Union (\( | \) or \( + \)), concatenation, Kleene star (\( * \)).

• Examples:

  • Strings ending with "ab": \( (a+b)^* ab \).

  • \( (0+1)^*(00+11)(0+1)^* \): strings containing two consecutive identical bits.

  • \( (011+1)^*(01)^* \): concatenation of blocks of "011" or "1", followed by any number of "01".

• Converting regex to FA: State elimination method:

  1. Create start state with \( \epsilon \)-transition to initial, final state with \( \epsilon \)-transitions from all finals.

  2. Eliminate states one by one, replacing paths through a state with direct regex on edges.

  3. Remaining regex on edge from new start to new final is the language.

Arden's Theorem

• Statement: For regex \( R \), if \( R = A + RB \), then \( R = AB^* \). (More generally, if \( X = A + XB \), then \( X = AB^* \), provided \( \epsilon \notin B \).)

• Proof idea: Solve iteratively: \( X = A + (A + XB)B = A + AB + XB^2 = \dots = A(B^* + B^* XB) \), so \( X = AB^* \).

• Application: Given FA, set up state equations:

  • For each state \( q_i \): \( q_i = \sum \delta(q_i, a) q_j \) (sum over transitions on \( a \)).

  • Solve for start state \( q_0 \) using Arden's theorem to get regex.

Closure Properties of Regular Languages

Regular languages are closed under:

• Union: \( L_1 \cup L_2 \): combine DFAs with new start and \( \epsilon \)-transitions.

• Intersection: \( L_1 \cap L_2 \): product DFA, final if both components final.

• Complement: \( \Sigma^* - L \): swap final/non-final states in DFA.

• Concatenation: \( L_1 L_2 \): from final states of \( L_1 \), \( \epsilon \)-transition to start of \( L_2 \).

• Kleene star: \( L^* \): add \( \epsilon \), \( \epsilon \)-transitions from finals to start, and from start to finals.

• Reversal: \( L^R \): reverse all edges, swap start and final (may need new start with \( \epsilon \)-transitions to old finals).

Pumping Lemma for Regular Languages

• Statement: If \( L \) is regular, \( \exists p > 0 \) (pumping length) such that any \( s \in L \) with \( |s| \ge p \) can be split \( s = xyz \) with:

  1. \( |y| > 0 \)

  2. \( |xy| \le p \)

  3. \( \forall i \ge 0, \; xy^iz \in L \).

• Proof sketch: From pigeonhole principle on states of DFA processing \( s \); \( y \) corresponds to loop.

• Application: Prove \( L = \{ a^n \mid n \text{ prime} \} \) not regular.

  Assume regular, let \( p \) be pumping length. Choose \( s = a^q \) where \( q \) is prime \( > p \). Split \( s = xyz \) with \( |xy| \le p \), \( |y| > 0 \). Let \( |y| = k \ge 1 \). Pump \( i=0 \): \( |xz| = q - k \). For \( i=2 \): \( |xy^2z| = q + k \). Both must be prime if \( L \) regular. But \( q-k \) and \( q+k \) differ by \( 2k \), and for large \( q \), one is composite (by Dirichlet? Actually, choose \( q \) such that \( q-k \) is composite). Contradiction.

• Also \( \{ a^n b^n \} \) not regular: pump \( a \)'s only, get unequal \( a \)'s and \( b \)'s.

Decision Problems for Regular Languages

All decidable:

• Membership: Simulate DFA on input.

• Emptiness: Check if any final state reachable from start (BFS/DFS).

• Finiteness: After removing unreachable states, check for cycles reachable from start to final.

• Equivalence: Minimize both DFAs and check isomorphism.

Converting Between FA and Regex

• State elimination: As above.

• Using Arden's theorem:

  1. Assign variable to each state.

  2. Write equations: \( q_i = \sum \delta(q_i, a) q_j \) (including \( \epsilon \) if \( q_i \) final).

  3. Solve for \( q_0 \) using Arden's theorem recursively.

III. Context-Free Grammars and Languages

Context-Free Grammar (CFG)

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

  • \( V \): variables (non-terminals)

  • \( T \): terminals

  • \( P \): productions of form \( A \to \alpha \), \( A \in V \), \( \alpha \in (V \cup T)^* \)

  • \( S \): start variable.

• Derivations:

  • Leftmost: always replace leftmost variable.

  • Rightmost: always replace rightmost variable.

• Parse Tree: Root \( S \), internal nodes variables, leaves terminals. Yield = string read left to right.

• Example: Grammar \( S \to SS \mid aSb \mid \epsilon \), string "abaabb":

  Parse tree: \( S \) splits into \( SS \). Left \( S \to aSb \to \epsilon \) gives "ab". Right \( S \to SS \), first \( S \to aSb \to \epsilon \) gives "ab", second \( S \to aSb \to \epsilon \) gives "ab"? Actually, need to derive "abaabb". Better: \( S \to SS \), left \( S \to aSb \to a \epsilon b = ab \), right \( S \to SS \), then \( S \to aSb \to aSb \to a \epsilon b = ab \), and last \( S \to \epsilon \)? That gives "abab". Not correct. Actually, "abaabb" has 2 a's, 4 b's? Let's count: a b a a b b? No, "abaabb" is a,b,a,a,b,b? That's 3 a's? Actually, "abaabb": positions: 1:a, 2:b, 3:a, 4:a, 5:b, 6:b → 3 a's, 3 b's? But grammar generates equal a and b? S→aSb adds one a and one b; S→SS concatenates; ε gives empty. So language is { a^n b^n | n even? } Actually, S→SS allows even concatenation. For n=3, can we get a^3 b^3? S→aSb → a aSb b → a a ε b b = aabb? That's n=2. For n=3: S→SS, first S→aSb→aεb=ab (n=1), second S→aSb→a aSb b→a a ε b b = aabb (n=2)? That gives ab aabb = abaabb? Yes! So first S gives "ab", second S gives "aabb", concatenated "abaabb". So parse tree: root S with two children S1 and S2. S1 → aSb → a ε b = ab. S2 → SS, with S21 → aSb → a ε b = ab, S22 → aSb → a ε b = ab? That gives ab ab = abab, not aabb. Actually, S2 needs to generate aabb. So S2 → aSb, then inside S → aSb → a ε b = ab, so S2 → a (ab) b = aabb. Yes. So tree: S → S1 S2; S1 → a S b → a ε b; S2 → a S b; that S → a S b → a ε b. So leaves: a, ε? Actually, ε production yields no leaf. So leaves: from S1: a, b; from S2: a, then from inner S: a, b, then b from outer S2. So order: a (S1), b (S1), a (S2 outer), a (inner S), b (inner S), b (S2 outer) → a b a a b b = "abaabb". Correct.

Ambiguity in CFG

• Definition: Grammar ambiguous if some string has multiple parse trees or multiple leftmost/rightmost derivations.

• Examples:

  • if-else: S → if S else S | if S | other → dangling else: if if else has two parses.

  • Given grammar: \( S \to aAB \), \( A \to bC \mid cd \), \( B \to c \mid d \), \( C \to cd \). String "acd":

    Derivation 1: \( S \to aAB \to a bC B \to a b cd B \to a b cd c \) → "abcdc"? Not "acd". Actually, to get "acd", we need: \( S \to aAB \to a A d \) (since \( B \to d \)), and \( A \to cd \), so \( a cd d = acdd \)? Not "acd". Maybe string "acd" not generated? Let's check: \( A \) can be \( bC \) or \( cd \). \( B \) can be \( c \) or \( d \). So \( aAB \) gives a followed by A then B. To get "acd", we need A to produce empty? But A has no ε. So maybe example is different. Past paper: "Check whether the grammar \( S \rightarrow aAB,\; A \rightarrow bC / cd,\; B \rightarrow c / d,\; C \rightarrow cd \) is ambiguous." Probably string "acd" is not generated. Maybe string "abcd"? Let's find ambiguous string. Actually, ambiguity often arises when there is choice in deriving terminals. For this grammar, consider string "acd": if A→cd and B→d, we get a c d d = "acdd". If A→bC and C→cd, and B→c, we get a b cd c = "abcdc". Not same. Maybe no ambiguity? But the question asks to check, so likely ambiguous. Perhaps string "abcd": from S→aAB, if A→bC→bcd, B→c → a bcd c = "abcdc"? Not "abcd". If A→cd, B→c → a cd c = "acdc". Not "abcd". Hmm. Maybe I misread. The grammar: A→bC|cd, so A can be "bcd" or "cd". B→c|d. So possible strings: a + (bcd or cd) + (c or d). So strings: abcdc, abcdd, acdc, acdd. Among these, "acdc" can be derived only one way? A→cd, B→c. "acdd": A→cd, B→d. "abcdc": A→bC→bcd, B→c. "abcdd": A→bC→bcd, B→d. So all have unique derivations? But wait, A→bC and C→cd gives "bcd", but is there another way? A→cd directly. So for string "bcd", A can derive via bC or directly? No, "bcd" is from A→bC→bcd. "cd" is from A→cd. So different strings. So no string has two derivations? But the grammar might be unambiguous. However, past paper asks to check, so maybe it is ambiguous due to C? C→cd only, so no choice. Perhaps the grammar is unambiguous. But the question might expect checking by trying strings. I'll skip specific example and give general method.

• Methods to remove ambiguity:

  • Refactor grammar to enforce associativity (e.g., left-factoring).

  • Introduce new variables to resolve conflicts.

  • Use precedence rules (e.g., for arithmetic expressions).

Normal Forms for CFG

• Chomsky Normal Form (CNF):

  • Productions: \( A \to BC \) or \( A \to a \) (and possibly \( S \to \epsilon \) if \( \epsilon \in L \)).

  • Conversion steps:

    1. Eliminate \( \epsilon \)-productions (except possibly \( S \to \epsilon \)): find nullable variables, add productions without them.

    2. Eliminate unit productions (\( A \to B \)): replace with all non-unit productions of \( B \).

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

    4. Break long productions: \( A \to B_1 B_2 \dots B_k \) (\( k \ge 3 \)) into \( A \to B_1 C_1, C_1 \to B_2 C_2, \dots, C_{k-2} \to B_{k-1} B_k \).

    5. Replace terminals in long productions with new variables.

• Greibach Normal Form (GNF):

  • Productions: \( A \to a \alpha \) where \( a \in T \), \( \alpha \in V^* \).

  • Conversion procedure:

    1. Convert to CNF.

    2. Order variables \( A_1, \dots, A_n \).

    3. For each \( A_i \), eliminate left recursion by substituting higher-ordered variables.

    4. Ensure right side starts with terminal.

Closure Properties of CFL

• Closed under: Union, concatenation, Kleene star, substitution (replace terminals with CFLs).

• Not closed under: Intersection, complement.

  • Counterexample: \( L_1 = \{ a^n b^n c^* \} \), \( L_2 = \{ a^* b^n c^n \} \) are CFLs, but \( L_1 \cap L_2 = \{ a^n b^n c^n \} \) not CFL (by pumping lemma).

• Proofs using PDAs:

  • Union: non-deterministically choose which PDA to simulate.

  • Concatenation: simulate first PDA, then second.

  • Star: simulate first PDA, then loop back.

Pumping Lemma for CFL

• Statement: If \( L \) is CFL, \( \exists p > 0 \) such that any \( s \in L \) with \( |s| \ge p \) can be split \( s = uvwxy \) with:

  1. \( |vwx| \le p \)

  2. \( |vx| > 0 \)

  3. \( \forall i \ge 0, \; u v^i w x^i y \in L \).

• Application: Prove \( L = \{ a^n b^n c^n \mid n \ge 1 \} \) not CFL.

  Assume CFL, let \( p \) be pumping length. Choose \( s = a^p b^p c^p \). Split \( s = uvwxy \) with \( |vwx| \le p \). Cases:

  • \( vwx \) within one block: pumping changes only that block, imbalance.

  • \( vwx \) spans two blocks: pumping disrupts balance (e.g., a's and b's only).

  Contradiction.

Decision Problems for CFL

• Membership: CYK algorithm (Cocke-Younger-Kasami) for CNF grammars: \( O(n^3) \) dynamic programming.

• Emptiness: Check if start symbol generates any terminal string (remove useless symbols).

• Finiteness: After removing useless symbols, check for cycles in dependency graph.

• Equivalence: Undecidable (no algorithm).

CFG Constructions for Specific Languages

• From regex: Convert regex to NFA, then to CFG (each state becomes variable, productions from transitions).

• Examples:

  • \( L = \{ a^m b^n c^{2m} d^n \mid m>0, n \ge 0 \} \):

    \( S \to AB \), \( A \to aAcc \mid \epsilon \) (gives \( a^m c^{2m} \)), \( B \to bBd \mid \epsilon \) (gives \( b^n d^n \)).

  • \( L = \{ w c w^R \mid w \in \{a,b\}^* \} \):

    \( S \to c \mid aSa \mid bSb \).

  • \( L = \{ a^r b^m c^n \mid r,m,n \ge 1 \} \):

    \( S \to aSc \mid T \), \( T \to bTd \mid \epsilon \)? Wait, need b's and c's independent? Actually, \( a^r b^m c^n \): no relation between counts. So \( S \to aS \mid A \), \( A \to bA \mid B \), \( B \to cB \mid \epsilon \). But that allows any order? We need all a's then b's then c's. So \( S \to aS \mid A \), \( A \to bA \mid B \), \( B \to cB \mid \epsilon \). That generates \( a^r b^m c^n \).

  • \( L = \{ a^n b^n c^{2n} d^n \} \):

    \( S \to aScd \mid T \), \( T \to ccT \mid \epsilon \)? Not exactly. Better: \( S \to aSc \mid U \), \( U \to bUd \mid \epsilon \), but c count? Actually, we need \( c^{2n} \). So combine: \( S \to aXc \), \( X \to aXc \mid Y \), \( Y \to bYd \mid \epsilon \). Then S generates \( a^{n+1} c^{n+1} \) from X? Let's derive: S→aXc, X→aXc | Y, Y→bYd|ε. For n=1: S→aYc→a ε c = ac (but we need a b c^2 d? No, for n=1, we need a^1 b^1 c^2 d^1? Actually, language is a^n b^n c^{2n} d^n. So for n=1: a b c c d. So we need one a, one b, two c's, one d. So S should produce a, then something, then c, but we need two c's. Perhaps: S→aBc, B→bBd | C, C→cC|ε? That gives a b^m c^{k} d^m with extra c's? Not clean. Alternative: S→aSc | T, T→bTd | ε, but then c count equals a count. To get 2n c's, we can have S→aSc | aSc? That would double? Actually, if we do S→aSc, we get a^n c^n. To get c^{2n}, we can have S→aSc | aSc? That would be ambiguous and give more c's? Not exactly. Use two non-terminals: S→aAc, A→aAc | B, B→bBd | ε. Then S: a followed by A then c. A generates a's and c's? A→aAc adds a and c, so if A generates k a's and k c's, then S gives a^{k+1} c^{k+1}. Still equal. So we need to generate two c's per a. So modify: S→aXc, X→aXc | Y, Y→bYd | ε. Then S: a, then X, then c. X can generate a's and c's equally, plus Y generates b's and d's. So total a's: 1 + (#a from X), c's: 1 + (#c from X) + ? Actually, X produces a's and c's in pairs, so if X produces m a's and m c's, then total a's: 1+m, c's: 1+m. But we need c's = 2*(a's). So not matching. We need c's twice a's. So we need to generate two c's per a. So for each a, we add two c's. So we can have S→aZc, Z→aZcc | ε? That would give for each a in Z, two c's? Let's see: S→aZc. If Z→ε, then S→a c (one a, one c). If Z→aZcc, then S→a (aZcc) c = aa Z c c c. So if Z→ε, we get a a c c c? That's two a's and three c's? Not consistent. Better: use separate non-terminals for a/c and b/d. Let S generate a's and c's with ratio 1:2, and separately b's and d's with ratio 1:1. So we can have S→A B, where A generates a^m c^{2m}, B generates b^n d^n. For A: we want to generate m a's and 2m c's. So we can do A→aAcc | ε. Check: A→ε gives m=0. A→aAcc: if A generates m a's and 2m c's, then aAcc gives (m+1) a's and (2m+2) c's. So by induction, A generates a^m c^{2m}. Perfect. For B: B→bBd | ε gives b^n d^n. So grammar: S→AB, A→aAcc | ε, B→bBd | ε. That works.

IV. Pushdown Automata

PDA Model

• Definition: \( M = (Q, \Sigma, \Gamma, \delta, q_0, z_0, F) \) or by empty stack (no final states).

  • \( Q \): states

  • \( \Sigma \): input alphabet

  • \( \Gamma \): stack alphabet

  • \( \delta: Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^*) \): transition relation

  • \( q_0 \): start state

  • \( z_0 \): initial stack symbol

  • \( F \): final states (if acceptance by final state).

• Instantaneous Description (ID): \( (q, w, \gamma) \) where \( q \) current state, \( w \) remaining input, \( \gamma \) stack content (top first).

• Acceptance:

  • By final state: After reading entire input, \( q \in F \).

  • By empty stack: After reading entire input, stack empty (\( \gamma = \epsilon \)).

Deterministic vs Non-deterministic PDA

• DPDA: For each \( (q, a, A) \), at most one transition. Also, if \( \delta(q, \epsilon, A) \) defined, then \( \delta(q, b, A) \) undefined for all \( b \in \Sigma \).

• NPDA: Multiple transitions allowed.

• Relation: \( \text{DCFL} \subsetneq \text{CFL} \).

  • Example: \( \{ a^n b^n \} \) is DCFL (DPDA: push a's, pop on b's).

  • Example: \( \{ w w^R \mid w \in \{a,b\}^* \} \) is CFL but not DCFL (requires guessing midpoint).

PDA Construction Techniques

• Linear languages: \( a^n b^n \): push a's, pop on b's.

• Palindromes:

  • Even length \( \{ w w^R \} \): non-deterministically guess midpoint, push first half, pop matching second half.

  • Odd length \( \{ w c w^R \} \): push until c, then pop matching.

• Copy languages: \( w w^R w \): more complex, use stack to store \( w \), then \( w^R \), then match last \( w \).

• Multiple counts:

  • \( a^n b^m c^n \): push a's, ignore b's, pop c's.

  • \( a^n b^{3n} \): on each \( a \), push three \( X \)'s; on each \( b \), pop one \( X \). Accept by empty stack.

Equivalence between CFG and PDA

• CFG → PDA (by empty stack):

  • PDA simulates leftmost derivation: stack holds current sentential form (top is leftmost variable).

  • Transitions: for production \( A \to \alpha \), pop \( A \), push \( \alpha \) (reverse order).

  • Start with \( S \) on stack. Accept when stack empty after input consumed.

• PDA → CFG:

  • For each pair of states \( (p,q) \), create variable \( A_{pq} \) generating strings taking PDA from \( p \) to \( q \) with stack unchanged except possibly popping initial symbol.

  • Productions from transitions: e.g., if \( \delta(p, a, A) \ni (r, BC) \), then \( A_{pq} \to a A_{rq} A_{?} \)... Standard construction is intricate; see standard textbooks.

Closure Properties of CFL via PDA

• Union: Non-deterministically choose which PDA to simulate.

• Concatenation: Simulate first PDA, then second.

• Kleene star: Simulate first PDA, then loop back (or use \( \epsilon \)-transition to restart).

• Not closed under intersection/complement: no PDA construction for intersection.

V. Turing Machines and Computability

Turing Machine (TM) Model

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

  • \( Q \): finite states

  • \( \Sigma \): input alphabet (does not contain blank \( B \))

  • \( \Gamma \supseteq \Sigma \cup \{B\} \): tape alphabet

  • \( \delta: Q \times \Gamma \to Q \times \Gamma \times \{L,R,S\} \)

  • \( q_0 \): start state

  • \( B \): blank symbol

  • \( F \): final states.

• Tape: Infinite in both directions, initially input on leftmost cells, rest blank.

• Head: Reads/writes, moves L/R/S.

TM Variants

• Multi-tape: Simulate by single tape using delimiters.

• Nondeterministic: Accept if some computation accepts.

• Multiple heads: Simulate with single tape.

• All equivalent to standard TM.

TM Construction Techniques

• Strategies: Marking symbols (change symbol to marked version), shuttling head (go back and forth), using multiple tracks (encode multiple symbols on one tape cell).

• Examples:

  • \( a^n b^n \): Scan right, mark first unmarked \( a \), go to rightmost unmarked \( b \), mark it, repeat. Accept if all a's and b's matched.

  • \( a^n b^n c^n \): Extend above: mark a's, match with b's, then match b's with c's.

  • Binary multiples of 3: Compute remainder mod 3 by scanning: start rem=0, for each bit, rem = (2*rem + bit) mod 3. Accept if rem=0.

  • Palindromes \( w c w^R \): Mark center \( c \), then move outward comparing symmetric symbols.

  • Multiplication: Implement school method: add multiplicand repeatedly, or use binary multiplication algorithm.

Language Classes

• Recursive (decidable): \( L = L(M) \) for some TM that halts on all inputs.

• Recursively Enumerable (r.e.): \( L = L(M) \) for some TM (may loop on reject).

• Co-r.e.: Complement is r.e.

Undecidability

• Halting Problem: \( HALT = \{ \langle M, w \rangle \mid M \text{ halts on } w \} \). Undecidable.

  • Proof: Reduction from self-halting or diagonalization. Assume decider \( H \), construct TM \( D \) that on input \( \langle M \rangle \) runs \( H(\langle M, \langle M \rangle \rangle) \) and loops if \( H \) accepts, halts if \( H \) rejects. Then \( D(\langle D \rangle) \) leads to contradiction.

• Other undecidable problems:

  • TM emptiness: \( EMPTY_{TM} = \{ \langle M \rangle \mid L(M) = \emptyset \} \).

  • TM equivalence: \( EQ_{TM} = \{ \langle M_1, M_2 \rangle \mid L(M_1) = L(M_2) \} \).

  • Post Correspondence Problem (PCP).

Post Correspondence Problem (PCP)

• Definition: Given dominoes \( (x_i, y_i) \) over alphabet \( \Sigma \), is there a sequence \( i_1, \dots, i_k \) such that \( x_{i_1} \dots x_{i_k} = y_{i_1} \dots y_{i_k} \)?

• Example: Dominoes: \( (0, 01), (100, 001), (110, 10) \). Try sequences: 1: 0 vs 01 no. 2: 100 vs 001 no. 3: 110 vs 10 no. 1,2: 0100 vs 01001? 0+100=0100, 01+001=01001 no. 2,3: 100110 vs 00110? 100+110=100110, 001+10=00110 no. 3,1: 1100 vs 100? 110+0=1100, 10+01=1001 no. 1,3,2: 0+110+100=0110100, 01+10+001=011001 no. Might not have solution. But PCP is undecidable in general.

• Undecidability: Reduce from TM acceptance.

VI. Complexity Theory

Complexity Classes

• P: Languages decidable by deterministic TM in polynomial time.

• NP: Languages decidable by nondeterministic TM in polynomial time; equivalently, problems where "yes" instances have polynomial-size certificates verifiable in polynomial time.

• NP-complete: \( L \in \text{NP} \) and every problem in NP reduces to \( L \) (NP-hard).

  • Examples: SAT, 3-SAT, CLIQUE, VERTEX COVER, HAMILTONIAN CYCLE.

• NP-hard: At least as hard as NP-complete problems; may not be in NP.

• P vs NP: Open problem. If P=NP, all NP problems have efficient algorithms.

Reductions

• Polynomial-time many-one reduction (Karp): \( L_1 \le_p L_2 \) if \( \exists \) computable \( f \) in poly time such that \( x \in L_1 \iff f(x) \in L_2 \).

• Used to show NP-hardness: reduce known NP-complete problem to new problem.

Cook-Levin Theorem

• SAT is NP-complete.

• Proof idea: Given nondeterministic TM and input, construct Boolean formula encoding accepting computation. Formula satisfiable iff TM accepts.

VII. Advanced Models and Hierarchies

Chomsky Hierarchy

[!TIP]

Note: CSL are closed under complement (proved by Immerman–Szelepcsényi), but not necessarily under Kleene star? Actually, CSL are closed under Kleene star as well.

Two-way Finite Automata (2-DFA)

• Head can move left or right on input tape (finite tape, no write).

• Equivalent to DFA (recognize regular languages), but state complexity may be exponential.

• Example: 2-DFA for \( \{ a^n b^n \} \) is impossible because it's not regular; but 2-DFA can recognize only regular languages.

Petri Nets

• Model: Bipartite directed graph:

  • Places (circles): hold tokens.

  • Transitions (bars): fire when input places have sufficient tokens.

  • Arcs: connect places to transitions and transitions to places.

• Firing: Transition fires by consuming tokens from input places and producing tokens in output places.

• Applications: Modeling concurrent systems, deadlock detection, workflow.

• Comparison with automata: Petri nets have parallel/concurrent behavior, infinite state space (unbounded tokens), while automata have sequential state transitions.

Universal Turing Machine

• Definition: A TM that takes as input \( \langle M, w \rangle \) (encoding of TM \( M \) and input \( w \)) and simulates \( M \) on \( w \).

• Significance:

  • Foundation of stored-program computers.

  • Proves existence of a single machine that can compute anything computable.

  • Used in undecidability proofs (e.g., reduction from universal TM halting).

VIII. Proof Techniques and Additional Topics

Mathematical Induction

• Principle: If \( P(0) \) true, and \( \forall k, P(k) \to P(k+1) \), then \( \forall n, P(n) \).

• Strong induction: Assume \( P(0), \dots, P(k) \) to prove \( P(k+1) \).

• Applications:

  • Proving closure properties (e.g., regular languages closed under union by induction on number of states).

  • Arden's theorem proof.

Diagonalization Argument

• Used to prove undecidability (e.g., halting problem).

• Idea: Assume list of all decidable languages, construct language not in list by differing on diagonal.

Reduction Techniques

• For undecidability: Reduce known undecidable problem (e.g., HALT) to new problem.

• For NP-completeness: Reduce known NP-complete problem (e.g., SAT) to new problem in polynomial time.

Decision Problems Summary

Common Constructions

• Composite machines (FA): Series/parallel combination.

• Residue mod N machines (Mealy/Moore): States = remainders 0..N-1, transition: new rem = (2*old + bit) mod N.

• Specific regex patterns:

  • Exactly two \( a \)'s over \( \{a,b\} \): \( b^* a b^* a b^* \).

  • \( \{ a^x \mid x \text{ divisible by 3 or 5} \} \): \( (aaa)^* + (aaaaa)^* \).

[!TIP]

Exam Focus: Past papers frequently ask for DFA/NFA conversion, regex from FA, CFG to CNF/GNF, PDA constructions for \( a^n b^n \), palindromes, TM for \( a^n b^n c^n \) or even 1's, pumping lemma applications, and undecidability proofs (halting problem). Practice these constructions thoroughly.