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

UNIT 5: THEORY OF COMPUTATION – SHORT NOTES

I. FINITE AUTOMATA & REGULAR LANGUAGES

Deterministic Finite Automata (DFA)

• 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 (deterministic)

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

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

• Operation: Reads input string symbol-by-symbol from left to right, transitions based on $\delta$. Accepts if final state after reading entire string is in $F$.

• Example: DFA for strings over $\{a,b\}$ ending with "ab".

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

  $$\displaystyle \delta(q_0,a)=q_0 $$, $$\displaystyle \delta(q_0,b)=q_0 $$, $$\displaystyle \delta(q_0,a)=q_1 $$? Wait, correction needed:

  Actually: $$\displaystyle q_0 \xrightarrow{a} q_0 $$, $$\displaystyle q_0 \xrightarrow{b} q_0 $$, $$\displaystyle q_0 \xrightarrow{a} q_1 $$? No.

  Standard: $$\displaystyle q_0 \xrightarrow{a} q_0 $$, $$\displaystyle q_0 \xrightarrow{b} q_0 $$; $$\displaystyle q_0 \xrightarrow{a} q_1 $$? Let's define properly:

  $$\displaystyle q_0 $$: no relevant suffix. On 'a' → $$\displaystyle q_1 $$ (suffix "a"), on 'b' → $$\displaystyle q_0 $$.

  $$\displaystyle q_1 $$: suffix "a". On 'a' → $$\displaystyle q_1 $$, on 'b' → $$\displaystyle q_2 $$ (suffix "ab").

  $$\displaystyle q_2 $$: suffix "ab" (final). On 'a' → $$\displaystyle q_1 $$, on 'b' → $$\displaystyle q_0 $$.

  Accepts if ends in $$\displaystyle q_2 $$.

Non-deterministic Finite Automata (NFA)

• Definition: 5-tuple $$\displaystyle M = (Q, \Sigma, \delta, q_0, F) $$ where $$\displaystyle \delta: Q \times (\Sigma \cup \{\epsilon\}) \rightarrow \mathcal{P}(Q) $$ (power set). Can have:

  • Multiple transitions for same symbol from a state.

  • ε-transitions (move without consuming input).

• Acceptance: String $w$ is accepted if there exists some path (sequence of choices) leading to a final state after reading $w$.

• Example: NFA for language over $\{a,b\}$ with no "aa" or "bb" (alternating symbols).

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

  $$\displaystyle \delta(q_0,a)=\{q_1\} $$, $$\displaystyle \delta(q_0,b)=\{q_1\} $$, $$\displaystyle \delta(q_1,a)=\{q_0\} $$, $$\displaystyle \delta(q_1,b)=\{q_0\} $$.

  Accepts alternating strings, including ε (if $$\displaystyle q_0 $$ is final).

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

• Procedure:

  1. DFA states = all subsets of NFA states (including $\emptyset$).

  2. Start state = $\epsilon$-closure$$\displaystyle (q_0) $$.

  3. For each DFA state $S$ (subset) and symbol $a$:

     • $$\displaystyle T = \bigcup_{q \in S} \delta(q,a) $$

     • New state = $\epsilon$-closure$(T)$.

  4. Final DFA states = any subset containing at least one NFA final state.

• Example: Convert given ε-NFA/NFA to DFA (see past paper: states $$\displaystyle \{q_0,q_1\} $$, $$\displaystyle \delta(q_0,a)=\{q_0,q_1\} $$, $$\displaystyle \delta(q_0,b)=\{q_0\} $$, $$\displaystyle \delta(q_1,b)=\{q_1\} $$, final $$\displaystyle q_1 $$).

  Start: $$\displaystyle \{q_0\} $$. On 'a': $$\displaystyle \{q_0,q_1\} $$ (new). On 'b': $$\displaystyle \{q_0\} $$.

  From $$\displaystyle \{q_0,q_1\} $$: on 'a': $$\displaystyle \{q_0,q_1\} $$, on 'b': $$\displaystyle \{q_0,q_1\} $$ (since $$\displaystyle \delta(q_1,b)=\{q_1\} $$).

  Final states: subsets containing $$\displaystyle q_1 $$ → $$\displaystyle \{q_0,q_1\} $$.

Regular Expressions (RE)

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

• Precedence: Star > Concatenation > Union.

• Examples:

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

  • Exactly two 'a's: $$\displaystyle b^* a b^* a b^* $$

  • $$\displaystyle L = \{a^x \mid x \text{ divisible by 3 or 5}\} $$: Complex; use union of $$\displaystyle (aaa)^* $$ and $$\displaystyle (aaaaa)^* $$ but careful with overlap. Typically: $$\displaystyle (aaa)^* + (aaaaa)^* $$ is not exact; need to combine. Better: $$\displaystyle (a^3)^* \cup (a^5)^* $$ but this includes multiples of 15 twice—still correct as RE. Simpler: $$\displaystyle (aaa)^* + (aaaaa)^* $$.

Arden’s Theorem

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

• Applications: Solving system of linear equations from automaton to find RE for language.

• Procedure:

  1. Write equations for each state: $$\displaystyle q_i = \sum \delta(q_i, a) q_j + \epsilon $$ if $$\displaystyle q_i $$ is final.

  2. Solve using Arden’s rule (substitute, eliminate).

• Example: For DFA with states $$\displaystyle q_1 $$ (start), $$\displaystyle q_2 $$ (final), transitions: $$\displaystyle q_1 \xrightarrow{a} q_1 $$, $$\displaystyle q_1 \xrightarrow{b} q_2 $$, $$\displaystyle q_2 \xrightarrow{a} q_2 $$, $$\displaystyle q_2 \xrightarrow{b} q_2 $$.

  Equations: $$\displaystyle q_1 = a q_1 + b q_2 + \epsilon $$, $$\displaystyle q_2 = a q_2 + b q_2 $$.

  Solve $$\displaystyle q_2 = (a+b)^* $$. Then $$\displaystyle q_1 = a q_1 + b (a+b)^* + \epsilon $$ → $$\displaystyle q_1 = a^* (b (a+b)^* + \epsilon) = a^* b (a+b)^* + a^* $$.

Closure Properties of Regular Languages

Regular languages are closed under:

[!TIP]

Common Pitfall: Forgetting to make DFA complete before complementing. Always add dead state if missing.

Minimization of DFA (Table-Filling Algorithm)

• Procedure:

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

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

  3. Unmarked pairs are equivalent → merge.

• Example: Minimize given DFA (see past paper: 6-state table).

  After marking, group equivalent states. E.g., if $$\displaystyle q_3 $$ and $$\displaystyle q_4 $$ unmarked and behave same, merge.

Finite Automata as Language Acceptors

• Language of FA: $$\displaystyle L(M) = \{ w \in \Sigma^* \mid \hat{\delta}(q_0, w) \in F \} $$ where $\hat{\delta}$ is extended transition.

• Acceptance: String is accepted if processing ends in final state.

• Rejection: Ends in non-final state or gets stuck (no transition).

Two-way Finite Automata (2DFA)

• Definition: Head can move left or right on tape (infinite in both directions). Transition: $$\displaystyle \delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\} $$.

• Comparison with DFA: 2DFA is more powerful in theory (can recognize non-regular languages? Actually, 2DFA still recognizes regular languages—same power as DFA, but may use fewer states. Proof: Can simulate 2DFA by DFA via subset construction over configurations).

• Key: Despite bidirectional movement, cannot count arbitrarily → still regular.

II. FINITE STATE MACHINES WITH OUTPUTS

Mealy Machine

• Definition: 6-tuple $$\displaystyle M = (Q, \Sigma, \Delta, \delta, \lambda, q_0) $$ where:

  • $\Delta$: Output alphabet.

  • $$\displaystyle \delta: Q \times \Sigma \rightarrow Q $$ (state transition).

  • $$\displaystyle \lambda: Q \times \Sigma \rightarrow \Delta $$ (output on transition).

• Output: Depends on current state and input symbol.

• Example: Binary residue mod 5.

  States: $$\displaystyle q_0 $$ (0), $$\displaystyle q_1 $$ (1), ..., $$\displaystyle q_4 $$ (4).

  On input bit $b$, new residue = $(2 \times \text{current} + b) \mod 5$.

  Output = new residue.

Moore Machine

• Definition: 6-tuple $$\displaystyle M = (Q, \Sigma, \Delta, \delta, \lambda, q_0) $$ where $$\displaystyle \lambda: Q \rightarrow \Delta $$ (output on state).

• Output: Depends only on current state.

• Example: Residue mod 3 for binary input.

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

  Transition: $$\displaystyle q_i \xrightarrow{b} q_{(2i+b) \mod 3} $$.

Conversion: Mealy ↔ Moore

• Mealy → Moore:

  1. For each Mealy state $q$, if outputs differ on different inputs, split $q$ into multiple Moore states $(q, \text{output})$.

  2. New Moore state output = output of incoming transition in Mealy.

• Moore → Mealy:

  1. Each Moore state $q$ with output $\lambda(q)$ becomes Mealy state.

  2. Mealy output on $(q,a)$ = $\lambda(\delta(q,a))$ (output of next state).

• Example: Convert given Mealy to Moore (past paper).

  If Mealy state $$\displaystyle q_0 $$ outputs 1 on '0' and 0 on '1', split into $$\displaystyle q_0^1 $$, $$\displaystyle q_0^0 $$.

Composite Machines

• Definition: Combine multiple FSMs in series/parallel to form complex system.

• Series (Cascade): Output of first feeds as input to second.

• Parallel: Same input to multiple machines, outputs combined.

• Example: Serial: Mealy for parity then Moore for mod 3.

III. CONTEXT-FREE GRAMMARS (CFG)

Definition & Components

• CFG: 4-tuple $$\displaystyle G = (V, T, P, S) $$:

  • $V$: Non-terminals (variables).

  • $T$: Terminals (alphabet).

  • $P$: Productions $$\displaystyle A \rightarrow \alpha $$ where $A \in V$, $$\displaystyle \alpha \in (V \cup T)^* $$.

  • $S \in V$: Start symbol.

• Examples:

  • $$\displaystyle S \rightarrow aSb \mid ab $$ generates $$\displaystyle \{a^n b^n \mid n \ge 1\} $$.

  • $$\displaystyle S \rightarrow SS \mid aSb \mid \epsilon $$ generates all balanced $a,b$ strings.

Derivations

• Leftmost derivation: Always replace leftmost non-terminal.

• Rightmost derivation: Always replace rightmost non-terminal.

• Example: For $$\displaystyle S \rightarrow aSb \mid ab $$, derive "aabb":

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

  Rightmost: $S \Rightarrow aSb \Rightarrow abSb?$ Wait:

  Rightmost: $S \Rightarrow aSb \Rightarrow aab b$? Actually:

  $$\displaystyle S \Rightarrow aSb \Rightarrow a aSb b \Rightarrow a a ab b = aabb $$.

Derivation Trees (Parse Trees)

• Construction: Root = $S$. Each internal node = non-terminal $A$, children = symbols in RHS of production $$\displaystyle A \rightarrow \alpha $$.

• Example: Grammar $$\displaystyle S \rightarrow SS \mid aSb \mid \epsilon $$, string "abaabb".

  Parse tree:

    S
  

   /|\
  

  S S
  

  /| |\

  a S b a b

  |
  

  ε
  

  Actually "abaabb" = a b a a b b? Wait, string "abaabb" has 6 symbols.

  Possible tree:

  $$\displaystyle S \rightarrow SS $$, left $$\displaystyle S \rightarrow aSb \rightarrow a \epsilon b = ab $$, right $$\displaystyle S \rightarrow aSb \rightarrow a aSb b \rightarrow a a \epsilon b b = aabb $$. So "ab"+"aabb" = "abaabb".

Ambiguity in Grammar

• Definition: Grammar is ambiguous if some string has >1 parse tree (or >1 leftmost/rightmost derivation).

• Example: Grammar $$\displaystyle S \rightarrow A1B $$, $$\displaystyle A \rightarrow 0A \mid \epsilon $$, $$\displaystyle B \rightarrow 0B \mid 1B \mid \epsilon $$.

  String "00101":

  Leftmost: $$\displaystyle S \Rightarrow A1B \Rightarrow 0A1B \Rightarrow 00A1B \Rightarrow 001B \Rightarrow 0010B \Rightarrow 00101 $$.

  Another: $$\displaystyle S \Rightarrow A1B \Rightarrow A01B \Rightarrow 0A01B \Rightarrow 001B \Rightarrow 0010B \Rightarrow 00101 $$.

  Two leftmost derivations → ambiguous.

Methods to Remove Ambiguity

• Enforce associativity/precedence: Rewrite grammar to eliminate multiple parses.

  • E.g., for arithmetic: $$\displaystyle E \rightarrow E+T \mid T $$, $$\displaystyle T \rightarrow T*F \mid F $$ (left-assoc).

• Introduce new non-terminals to enforce grouping.

Normal Forms for CFG

Chomsky Normal Form (CNF)

• Productions: $$\displaystyle A \rightarrow BC $$ (two non-terminals) or $$\displaystyle A \rightarrow a $$ (terminal). Optionally $$\displaystyle S \rightarrow \epsilon $$ if $\epsilon \in L$.

• Conversion Procedure:

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

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

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

  4. Convert to binary: Replace $$\displaystyle A \rightarrow B_1 B_2 ... B_k $$ ($$\displaystyle k>2 $$) with $$\displaystyle A \rightarrow B_1 X_1 $$, $$\displaystyle X_1 \rightarrow B_2 X_2 $$, ..., $$\displaystyle X_{k-2} \rightarrow B_{k-1} B_k $$.

  5. Replace terminals in long productions: If $$\displaystyle A \rightarrow a \alpha $$ with $\alpha$ non-terminals, introduce $$\displaystyle A \rightarrow aY $$, $$\displaystyle Y \rightarrow \alpha $$.

• Example: Convert $$\displaystyle S \rightarrow AB \mid a $$, $$\displaystyle A \rightarrow a $$, $$\displaystyle B \rightarrow b $$. Already in CNF.

Greibach Normal Form (GNF)

• Productions: $$\displaystyle A \rightarrow a \alpha $$ where $a \in T$, $$\displaystyle \alpha \in V^* $$ (possibly $\epsilon$).

• Conversion Procedure:

  1. Order non-terminals $$\displaystyle A_1, A_2, ..., A_n $$.

  2. For each $$\displaystyle A_i $$, eliminate productions with $$\displaystyle A_j $$ ($$\displaystyle j<i $$) on RHS by substitution.

  3. Ensure each production starts with terminal.

• Example: Convert $$\displaystyle S \rightarrow ABA \mid AB \mid BA \mid AA \mid B $$, $$\displaystyle A \rightarrow aA \mid a $$, $$\displaystyle B \rightarrow bB \mid b $$.

  After ordering and substitution, get GNF.

Properties of Context-Free Languages

• Closure: Union, concatenation, Kleene star. Not closed under intersection, complement.

• Pumping Lemma for CFL:

  If $L$ is CFL, $\exists p$ (pumping length) s.t. $\forall z \in L$ with $|z| \ge p$, $$\displaystyle z = uvwxy $$ with:

  1. $|vwx| \le p$,

  2. $|vx| \ge 1$,

  3. $\forall i \ge 0$, $$\displaystyle uv^i w x^i y \in L $$.

• Example: Prove $$\displaystyle L = \{a^n b^n c^n \mid n \ge 1\} $$ not CFL.

  Assume CFL, let $p$ be pumping length. Take $$\displaystyle z = a^p b^p c^p $$.

  $vwx$ spans at most two types of symbols. Pumping changes counts unevenly → not in $L$.

Regular Grammars

• Right-linear: $$\displaystyle A \rightarrow aB $$ or $$\displaystyle A \rightarrow a $$ (or $\epsilon$).

• Left-linear: $$\displaystyle A \rightarrow Ba $$ or $$\displaystyle A \rightarrow a $$.

• Equivalence: Both generate exactly regular languages.

IV. PUSHDOWN AUTOMATA (PDA)

PDA Model

• Definition: 7-tuple $$\displaystyle M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F) $$:

  • $Q$: States.

  • $\Sigma$: Input alphabet.

  • $\Gamma$: Stack alphabet.

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

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

  • $$\displaystyle 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 (top first).

Modes of Acceptance

1. By final state: Accept if after reading input, $q \in F$ (stack can be anything).

2. By empty stack: Accept if stack becomes empty (state can be any).

• Equivalence: For any PDA, can modify to accept by empty stack or final state. But DPDA by empty stack ≠ DPDA by final state in power.

Deterministic PDA (DPDA) vs NPDA

• DPDA: $\delta$ is a function (at most one move for any $(q,a,\gamma)$). No choice between ε-move and symbol move.

• NPDA: $\delta$ is a relation → multiple choices.

• Example: $$\displaystyle L = \{a^n b^n \mid n \ge 1\} $$ is deterministic CFL (DCFL).

  DPDA: Push on 'a', pop on 'b', reject if 'b' seen before 'a' or stack empty prematurely.

• Key: All regular languages are DCFL, but some CFLs are not deterministic (e.g., $$\displaystyle \{a^i b^j c^k \mid i=j \text{ or } j=k\} $$).

Design of PDA for Languages

• Techniques:

  • Matching counts: Push for first symbol(s), pop for matching second.

  • Palindromes: Non-deterministically guess midpoint, then pop matching.

  • Multiple stacks: Simulate TM with two stacks.

• Examples:

  1. $$\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_f, \epsilon) $$ (accept by empty stack).

  2. Even-length palindromes over $\{a,b\}$:

     Non-deterministically push first half (marking with ε-moves), then pop matching second half.

Conversion: CFG ↔ PDA

• CFG → PDA (by empty stack):

  • PDA simulates leftmost derivation.

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

  • For production $$\displaystyle A \rightarrow \alpha $$, when $A$ on top, pop $A$, push $\alpha$ (reverse order).

  • Accept by empty stack.

• PDA → CFG:

  • For each pair of states $(p,q)$, create variable $[p q]$ generating strings taking PDA from $p$ to $q$ with empty stack.

  • Add productions based on transitions.

• Example: Convert given CFG to PDA (past paper: $$\displaystyle S \rightarrow aABB \mid AAA $$, etc.).

  PDA: Start with $S$ on stack. For $$\displaystyle S \rightarrow aABB $$, when $S$ on top, pop $S$, push $BBA$ (reverse of $ABB$? Actually push in reverse: $B,B,A$). Then process terminals by matching input.

V. TURING MACHINES (TM)

TM Model

• Definition: 7-tuple $$\displaystyle M = (Q, \Sigma, \Gamma, \delta, q_0, B, F) $$:

  • $Q$: Finite states.

  • $\Sigma$: Input alphabet (no blank $B$).

  • $\Gamma \supseteq \Sigma \cup \{B\}$: Tape alphabet.

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

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

  • $B$: Blank symbol.

  • $F \subseteq Q$: Final states.

• Tape: Infinite in both directions, initially input on tape, rest blanks.

• Acceptance: Entering a final state after halting.

Techniques for TM Construction

1. Marking symbols: Change symbol to mark visited (e.g., $$\displaystyle a \rightarrow X $$).

2. Multiple tracks: Use tape symbols as pairs $(a,b)$ to simulate multiple tapes.

3. Counters: Use portion of tape as counter (unary or binary).

4. Back-and-forth scanning: Move left/right to compare sections.

5. Simulation: Simulate other automata (PDA, etc.).

Design of TM for Specific Languages

• General approach:

  1. Scan to find pattern.

  2. Mark processed symbols.

  3. Compare counts (e.g., for $$\displaystyle a^n b^n $$).

  4. Loop until all matched.

• Examples:

  1. Even number of 1's:

     State $$\displaystyle q_0 $$ (even), $$\displaystyle q_1 $$ (odd). On reading 1, flip state. Accept in $$\displaystyle q_0 $$ at end.

  2. $$\displaystyle a^n b^n $$:

     Mark leftmost $a$ as $X$, find first unmarked $b$, mark as $Y$, repeat. Reject if $b$ missing or extra $a$.

  3. $$\displaystyle a^n b^n c^n $$:

     More complex: Mark $a$ as $X$, then find matching $b$ mark $Y$, then matching $c$ mark $Z$. Repeat. Need to ensure order.

  4. $$\displaystyle W C W^R $$ (over $\{0,1\}$):

     Mark first symbol of $W$, move right to $C$, then compare with last symbol of $W$ (from right). Use two markers.

  5. Multiple of 3 (binary):

     Remainder method: States $$\displaystyle q_0,q_1,q_2 $$ (remainder mod 3). On each bit $b$, new remainder = $(2 \times \text{current} + b) \mod 3$. Accept if final remainder 0.

Variations of Turing Machines

• Multi-tape TM: Multiple tapes, independent heads. Equivalent to single-tape (can simulate with tracks).

• Non-deterministic TM (NTM): $\delta$ returns set of moves. Equivalent to deterministic TM (simulate all branches in sequence).

Universal Turing Machine (UTM)

• Concept: A TM $U$ that takes as input encoding of any TM $M$ and string $w$, and simulates $M$ on $w$.

• Significance: Shows existence of general-purpose computer. Foundation of computability theory.

• Encoding: Describe $M$’s states, alphabet, transition table as string over some alphabet.

VI. DECIDABILITY & UNDECIDABILITY

Language Classes

• Relationships: Recursive ⊂ RE. Recursive = RE ∩ co-RE.

Decidable Problems

• For Regular Languages: Emptiness, finiteness, membership, equivalence (via DFA minimization).

• For CFLs: Emptiness, finiteness, membership (via CYK algorithm), but equivalence undecidable.

• Example: Emptiness for DFA: Check if any final state reachable from start.

Undecidable Problems

Halting Problem (HP)

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

• Proof (reduction from Acceptance Problem):

  1. Assume $H$ decidable by TM $$\displaystyle H_{dec} $$.

  2. Construct $D$ that on input $\langle M, w \rangle$:

     • Run $$\displaystyle H_{dec}(\langle M, w \rangle) $$.

     • If $$\displaystyle H_{dec} $$ says "halts", loop; if "loops", accept.

  3. Then $D$ on $\langle D \rangle$ leads to contradiction.

• Consequence: No general algorithm to check if TM halts.

Post Correspondence Problem (PCP)

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

• Example: Pairs: $(ba, bab), (abb, bb), (bab, abb)$.

  Try: $$\displaystyle ba \cdot bab \cdot abb = babababb $$ vs $$\displaystyle bab \cdot abb \cdot bb = bababbb $$? Not equal.

  No solution? Check systematically. Often solved by trial.

• Undecidability: Reduction from TM acceptance.

Other Undecidable Problems

• Emptiness for TM: $$\displaystyle \{ \langle M \rangle \mid L(M) = \emptyset \} $$ undecidable.

• Equivalence for TM: $$\displaystyle \{ \langle M_1, M_2 \rangle \mid L(M_1)=L(M_2) \} $$ undecidable.

• Regularity for TM: $\{ \langle M \rangle \mid L(M) \text{ regular} \}$ undecidable.

Reductions for Undecidability Proofs

• Technique: Reduce known undecidable problem $A$ to problem $B$. If $B$ decidable, then $A$ decidable → contradiction.

• Steps:

  1. Instance of $A$: $x$.

  2. Construct in poly-time instance $f(x)$ of $B$ such that $x \in A \iff f(x) \in B$.

  3. If $B$ decidable, then $A$ decidable.

VII. COMPUTATIONAL COMPLEXITY

Complexity Classes

• P: Problems solvable by deterministic TM in polynomial time.

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

• NP: Problems solvable by non-deterministic TM in polynomial time, or verifiable in polynomial time by deterministic TM given a certificate.

  • Examples: SAT, 3-SAT, Clique, Vertex Cover, TSP (decision version).

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

NP-Complete and NP-Hard

• NP-Complete:

  1. In NP.

  2. NP-hard: Every problem in NP reduces to it.

  • Examples: SAT (Cook-Levin), 3-SAT, Clique, Vertex Cover, Hamiltonian Cycle.

• NP-Hard: At least as hard as NP-complete, but not necessarily in NP.

  • Examples: Halting problem, optimization versions (TSP min distance), undecidable problems.

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

P vs NP Problem

• Open question: Does $$\displaystyle P = NP $$?

• Implications: If $$\displaystyle P = NP $$, many hard problems become efficiently solvable. Widely believed $P \neq NP$.

VIII. ADVANCED TOPICS

Chomsky Hierarchy of Grammars

• Inclusions: Regular ⊂ CFL ⊂ CSL ⊂ RE. Proper containments known.

Petri Nets Model

• Components:

  • Places (circles): Conditions, hold tokens.

  • Transitions (rectangles): Events.

  • Arcs: Connect places to transitions (and vice versa) with weights.

  • Tokens (dots): Marking represents state.

• Firing rule: Transition fires if each input place has ≥ weight tokens; consumes tokens from input places, produces to output places.

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

Mathematical Induction in Computability Proofs

• Used to prove properties of languages/automata by induction on string length or derivation steps.

• Example: Prove that for CFG in CNF, parse tree with $n$ leaves has height $$\displaystyle \ge \log_2 n $$.

Pumping Lemma for Regular Languages

• Statement: If $L$ regular, $$\displaystyle \exists p>0 $$ (pumping length) s.t. $\forall w \in L$ with $|w| \ge p$, $$\displaystyle w = xyz $$ with:

  1. $|xy| \le p$,

  2. $|y| \ge 1$,

  3. $\forall i \ge 0$, $$\displaystyle xy^i z \in L $$.

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

  Assume regular, let $p$. Choose $$\displaystyle w = a^q $$ where $q$ is prime $$\displaystyle > p $$. Then $$\displaystyle w = xyz $$, $$\displaystyle |y| = k \ge 1 $$. Pump $$\displaystyle i=2 $$: $$\displaystyle |w'| = q+k $$. If $$\displaystyle k>0 $$, $q+k$ composite for large $q$? Not necessarily. Better: Choose $$\displaystyle w = a^{p!} $$ (factorial). Then $$\displaystyle |y| = m \le p $$, so $m$ divides $p!$. Pump $$\displaystyle i = p!/m + 1 $$: length = $$\displaystyle p! + (p!/m)m = 2 p! $$, composite → not prime → $w' \notin L$. Contradiction.

Composite Machines (from FSM combinations)

• Series: Output of first is input to second.

• Parallel: Same input to multiple FSMs, outputs combined via function.

• Example: Parity checker (Mealy) followed by mod-3 counter (Moore).

Residue Modulo Problems

• Binary number mod $k$: Use DFA/Mealy/Moore with $k$ states representing remainder $0,...,k-1$.

• Transition: On bit $b$, new remainder = $(2 \times \text{current} + b) \mod k$.

• Example: Mod 5 (14-state DFA? Actually 5 states).

  States $$\displaystyle q_0..q_4 $$. From $$\displaystyle q_i $$ on $b$: $$\displaystyle q_{(2i+b) \mod 5} $$.

[!EXAM TIPS]

1. NFA to DFA: Always compute $\epsilon$-closure first for ε-NFA.

2. Arden’s Theorem: Solve equations in order of dependency; eliminate variables.

3. CFG to CNF: Eliminate ε first, then unit productions, then long/teminal productions.

4. PDA Design: Clearly state acceptance mode (final state or empty stack).

5. TM Construction: Use markers (e.g., $X$ for visited $a$) and systematic scanning.

6. Undecidability Proofs: Reduce from Halting Problem or Acceptance Problem.

7. Pumping Lemma: Choose $w$ cleverly (often $$\displaystyle a^p b^p $$ for CFL, $$\displaystyle a^p $$ for regular).

8. Mealy vs Moore: Output on transition vs state. Conversion: split states in Mealy→Moore.

9. Minimization: Table-filling—mark distinguishable pairs first.

10. Ambiguity: Find string with two leftmost derivations or parse trees.