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

UNIT 3: Theory of Computation – Short Notes

I. FINITE AUTOMATA (FA) & MACHINES WITH OUTPUT

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$: 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: $$\displaystyle L(M) = \{ w \in \Sigma^* \mid \hat{\delta}(q_0, w) \in F \} $$, where $\hat{\delta}$ is the extended transition function.

• Design Examples:

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

  • Strings with exactly two a's and two b's.

  • Strings with neither aa nor bb as substrings.

• [!TIP] Exam Tip: For design problems, identify key substrings/patterns and create states to "remember" progress toward acceptance. Always include a dead/trap state for undefined transitions.

Non-deterministic Finite Automaton (NFA) & ε-NFA

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

  • $\epsilon$-NFA allows $\epsilon$-transitions (moves without consuming input).

• Language Acceptance: $w \in L(M)$ iff there exists some path from $$\displaystyle q_0 $$ to a state in $F$ consuming $w$.

• ε-closure: For a state $q$, $\epsilon$-closure$(q)$ is the set of states reachable from $q$ via only $\epsilon$-transitions (including $q$ itself). For a set $S$, it's the union of $\epsilon$-closure of all states in $S$.

• Design Examples: Construct NFA from regular expressions (e.g., for (0+1)*00(0+1)*).

Equivalence & Conversion

• Subset Construction: Converts an NFA/ε-NFA to an equivalent DFA.

  1. DFA states are subsets of NFA states.

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

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

  4. A DFA state is final if it contains any NFA final state.

• Proof of Equivalence: Both accept exactly the same language. The DFA simulates all possible NFA computations in parallel.

DFA Minimization

• Goal: Find the DFA with the smallest number of states accepting $L(M)$.

• Table-Filling/Partitioning Method:

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

  2. For each unmarked pair $(p, q)$ and each $a \in \Sigma$, if $(\delta(p,a), \delta(q,a))$ is marked, then mark $(p,q)$.

  3. Repeat step 2 until no new marks.

  4. Unmarked pairs are indistinguishable and can be merged.

• Distinguishable States: Two states $p, q$ are distinguishable if there exists a string $w$ such that starting from $p$ and $q$ on $w$, one ends in a final state and the other does not.

• [!TIP] Common Pitfall: After merging states, ensure the resulting transition function is deterministic and complete. The minimized DFA is unique up to state renaming.

Finite Automata with Outputs

• Mealy Machine:

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

  • Output Function: $$\displaystyle \lambda: Q \times \Sigma \rightarrow \Delta $$ (output depends on current state and input).

  • Example: Binary residue mod 5 machine. States represent residues 0-4. Transition on input bit $b$: new residue = $(2 \times \text{current} + b) \mod 5$. Output is the new residue.

• Moore Machine:

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

  • Output Function: $$\displaystyle \lambda: Q \rightarrow \Delta $$ (output depends only on current state).

  • Example: Binary residue mod 3 machine. States 0,1,2. Output = state value.

• Conversion:

  • Mealy → Moore: For each state with different outputs on different inputs, split the state into multiple states, each associated with one output.

  • Moore → Mealy: Assign to each transition the output of the destination state.

• [!TIP] Key Difference: In Mealy, output is immediate (on transition); in Moore, output is delayed (on state). Mealy machines often have fewer states.

Composite Machines & Two-way DFA

• Composite Machines: Construct complex FSM by connecting simpler ones in series (output of one feeds input of next) or parallel (merge states with same input/output behavior).

• Two-way Finite Automata (2-DFA):

  • Definition: DFA with a two-way read head that can move left (L) or right (R) on a finite tape with end markers.

  • Transition Function: $$\displaystyle \delta: Q \times \Gamma \rightarrow Q \times \{L, R\} $$, where $$\displaystyle \Gamma = \Sigma \cup \{\vdash, \dashv\} $$ (left/right end markers).

  • Power: 2-DFA recognize exactly the regular languages (same as 1-DFA), but can be more succinct (fewer states for some languages).

II. REGULAR LANGUAGES & EXPRESSIONS

Regular Expressions (RE)

• Operators: Union (| or +), concatenation, Kleene star (*). Precedence: star > concat > union. Parentheses for grouping.

• Constructing RE:

  • Strings over $\{a,b\}$ ending with ab: (a+b)*ab.

  • Exactly two a's: b*ab*ab*b*.

  • Length divisible by 3 or 5: ((aaa+bbbbb)*)? (Careful: union of two separate conditions). Correct: ( (aaa)* | (bbbbb)* ) but this includes empty string. For non-empty: (aaa+bbbbb)(aaa+bbbbb)*? Actually, need all strings where length mod 3=0 OR mod 5=0. A correct RE is complex; often use ( (aaa)* | (bbbbb)* ) but this misses strings like aaaaa (length 5, not multiple of 3). Better: ( (aaa)* (ε+ a + aa) | (bbbbb)* (ε+ b + bb + bbb + bbbb) )? This is messy. A simpler approach: ( (aaa)* | (bbbbb)* ) accepts lengths that are multiples of 3 or multiples of 5, but also accepts strings that are multiples of both (e.g., 15). That's fine. But it also accepts the empty string. If empty string not allowed, add (a+b)+? No. Actually, ( (aaa)* | (bbbbb)* ) is correct for the language including empty string. For non-empty, ( (aaa)+ | (bbbbb)+ ) but this misses strings like a (length 1, not multiple of 3 or 5). So the language is all strings whose length is a multiple of 3 or 5. The RE is: ( (aaa)* | (bbbbb)* ) works because it generates all strings of length 3k or 5k. But note: aaa is length 3, aaaaaa length 6, etc. bbbbb length 5, bbbbbbbbbb length 10. But what about a string of length 8? Not accepted. Good. But what about a string of length 15? Both parts can generate it? (aaa)* generates 15 as aaaaa...? 15 is multiple of 3, so (aaa)* generates aaaaaaaaaaaaaaa (15 a's). But the language is over {a,b}, so any combination of a's and b's? The problem statement: "strings where length divisible by 3 or 5" means the total length of the string, regardless of symbols. So a string of length 6 with any mix of a's and b's is accepted. So the RE must generate all strings of length multiple of 3 or 5. That is: ( (a+b)^3 | (a+b)^5 )*? But that would generate concatenations of blocks of 3 or 5, which gives lengths that are sums of 3s and 5s, not necessarily multiples of 3 or 5 individually. For example, (a+b)^3 (a+b)^5 gives length 8, which is not multiple of 3 or 5. So incorrect. The correct RE is more complex. Actually, the set of lengths that are multiples of 3 or 5 is a regular set (since it's the union of two arithmetic progressions). The RE can be built using the fact that (a+b)^n denotes all strings of length n. So the language is $$\displaystyle \bigcup_{k=0}^\infty (a+b)^{3k} \cup \bigcup_{k=0}^\infty (a+b)^{5k} $$. This is regular. A standard method: use the product construction for the DFA with 15 states (lcm(3,5)=15) and then convert to RE. But for exam, they might expect: ( ( (a+b)(a+b)(a+b) )* | ( (a+b)(a+b)(a+b)(a+b)(a+b) )* ). That's acceptable. But note: this includes empty string. If empty string not in language, then ( ( (a+b)(a+b)(a+b) )+ | ( (a+b)(a+b)(a+b)(a+b)(a+b) )+ ). But careful: (a+b)^3 means any string of length 3. So ((a+b)^3)* generates all strings whose length is a multiple of 3. Similarly for 5. So the union is correct.

• RE from DFA: Use state elimination method (also called generalized transition graph method). Steps:

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

  2. Eliminate non-start/non-final states one by one, updating edge labels with REs.

  3. The final RE is the label on the direct edge from new start to new final.

Arden's Theorem

• Statement: For a system of linear equations over regular expressions, if $R$ and $S$ are REs and $R$ does not contain $\epsilon$, then the equation $$\displaystyle X = R X | S $$ has a unique solution $$\displaystyle X = R^* S $$.

• Application to FA → RE:

  1. For each state $$\displaystyle q_i $$, write an equation: $$\displaystyle q_i = \sum_{q_j} q_j a_{ji} | \epsilon $$ if $$\displaystyle q_i $$ is start state, else without $\epsilon$.

  2. Solve the system using Arden's theorem (substitute and simplify).

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

  Equations: $$\displaystyle q_0 = q_0 a | q_1 b | \epsilon $$, $$\displaystyle q_1 = q_0 a | q_1 a | q_1 b $$.

  Solve: $$\displaystyle q_1 = (a+b)^* q_0 a $$? Let's do properly.

  $$\displaystyle q_1 = q_0 a + q_1 (a+b) \Rightarrow q_1 = (a+b)^* q_0 a $$.

  Then $$\displaystyle q_0 = q_0 a + q_1 b + \epsilon = q_0 a + ( (a+b)^* q_0 a ) b + \epsilon = q_0 (a + (a+b)^* a b) + \epsilon $$.

  So $$\displaystyle q_0 = (a + (a+b)^* a b)^* $$.

  Final RE: $$\displaystyle q_0 $$ since $$\displaystyle q_0 $$ is start and $$\displaystyle q_1 $$ is final? Actually, language is all strings reaching $$\displaystyle q_1 $$. So $$\displaystyle L = q_1 $$? But $$\displaystyle q_1 $$ is expressed in terms of $$\displaystyle q_0 $$. So $$\displaystyle L = (a+b)^* q_0 a $$. Substitute $$\displaystyle q_0 $$: messy. Better to eliminate states. But Arden's gives $$\displaystyle q_0 $$ as above. Then $$\displaystyle L = q_0 (a+b)^* a $$? Not exactly. Since $$\displaystyle q_1 $$ is final, $$\displaystyle L = q_1 $$. So $$\displaystyle L = (a+b)^* q_0 a $$. But $$\displaystyle q_0 $$ includes $\epsilon$, so $$\displaystyle L = (a+b)^* a $$? That can't be right because from start, b goes to $$\displaystyle q_1 $$ directly. So b should be accepted. Check: b is in $$\displaystyle q_1 $$? From $$\displaystyle q_0 $$ on b to $$\displaystyle q_1 $$, so yes. But $$\displaystyle (a+b)^* a $$ does not generate b. So error. Let's re-derive equations correctly.

  Standard: For each state $i$, equation: $$\displaystyle q_i = \sum_{j} q_j a_{ji} \cup \{\epsilon\} $$ if $i$ is start.

  Here: $$\displaystyle q_0 $$ start: $$\displaystyle q_0 = q_0 a \cup q_1 b \cup \epsilon $$.

  $$\displaystyle q_1 $$ not start: $$\displaystyle q_1 = q_0 a \cup q_1 a \cup q_1 b $$.

  Solve $$\displaystyle q_1 $$: $$\displaystyle q_1 = q_0 a \cup q_1 (a+b) \Rightarrow q_1 = (a+b)^* q_0 a $$.

  Then $$\displaystyle q_0 = q_0 a \cup ( (a+b)^* q_0 a ) b \cup \epsilon = q_0 (a \cup (a+b)^* a b) \cup \epsilon $$.

  So $$\displaystyle q_0 = (a \cup (a+b)^* a b)^* $$.

  Now $$\displaystyle L = q_1 $$ (since $$\displaystyle q_1 $$ final) = $$\displaystyle (a+b)^* q_0 a = (a+b)^* (a \cup (a+b)^* a b)^* a $$.

  This is complicated. But for exam, they might expect simpler examples.

• [!TIP] Arden's Tip: Write equations in the form $$\displaystyle X = R X + S $$. Isolate $X$ on left. Ensure $R$ does not contain $\epsilon$ (if it does, factor appropriately). Solve recursively from equations with no unknowns on right.

Closure Properties of Regular Languages

Regular languages are closed under:

• Union: $$\displaystyle L_1 \cup L_2 $$ – construct DFA with new start state branching to $$\displaystyle M_1 $$ and $$\displaystyle M_2 $$.

• Intersection: $$\displaystyle L_1 \cap L_2 $$ – product construction: states are pairs $(p,q)$, accept if both components accept.

• Complement: $$\displaystyle \Sigma^* - L $$ – swap final and non-final states in DFA (must be complete).

• Concatenation: $$\displaystyle L_1 L_2 $$ – add $\epsilon$-transitions from final states of $$\displaystyle M_1 $$ to start of $$\displaystyle M_2 $$ (NFA), then convert to DFA.

• Kleene Star: $$\displaystyle L^* $$ – add $\epsilon$-transition from new start to old start, from old finals to old start, and from new start to new final.

• Reversal: $$\displaystyle L^R $$ – reverse all transitions, swap start and final (now a set), convert NFA to DFA.

• Homomorphism & Inverse Homomorphism: Regular.

Pumping Lemma for Regular Languages

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

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

  2. $|xy| \leq p$

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

• Application to Prove Non-Regular:

  • Assume $L$ is regular, let $p$ be pumping length.

  • Choose a specific string $s \in L$ with $|s| \geq p$ (usually of the form $$\displaystyle a^p b^p $$ or $$\displaystyle a^p $$).

  • Show that for all possible decompositions $$\displaystyle s=xyz $$ with $$\displaystyle |y|>0 $$ and $|xy|\leq p$, there exists some $i$ (usually $$\displaystyle i=0 $$ or $$\displaystyle i=2 $$) such that $$\displaystyle xy^iz \notin L $$.

  • Contradiction $\Rightarrow$ $L$ not regular.

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

  • Choose $$\displaystyle s = a^p $$ where $p$ is a prime $$\displaystyle > p $$? But $p$ is pumping length. Choose $$\displaystyle s = a^q $$ where $q$ is a prime $$\displaystyle > p $$.

  • Then $$\displaystyle s = xyz $$, $|xy| \leq p$, so $$\displaystyle y = a^k $$, $1 \leq k \leq p$.

  • Pump down ($$\displaystyle i=0 $$): $$\displaystyle s' = a^{q-k} $$. Since $q$ is prime and $$\displaystyle k < q $$, $q-k$ is composite (if $$\displaystyle q-k>1 $$) or 0 or 1. But $q-k$ may be prime? For example, $$\displaystyle q=7, k=2 $$, then $5$ is prime. So not guaranteed composite. This language is actually not regular, but pumping lemma proof is tricky because primes are not closed under subtraction. A better example: $$\displaystyle L = \{ a^n b^n \mid n \geq 0 \} $$ is not regular (but that's CFL). For regular, use $$\displaystyle L = \{ a^{n^2} \mid n \geq 0 \} $$ or $$\displaystyle L = \{ a^p \mid p \text{ prime} \} $$ requires more advanced argument (using closure under intersection with $$\displaystyle a^* $$ and pumping lemma on the resulting set). Actually, the standard example is $$\displaystyle L = \{ a^n b^n \} $$ for CFL pumping. For regular, common examples: $$\displaystyle L = \{ a^n b^n \} $$, $$\displaystyle L = \{ a^n \mid n \text{ is prime} \} $$ (but proof uses closure and pumping on $$\displaystyle L \cap a^* = \{ a^p \mid p \text{ prime} \} $$ and then show that pumping yields non-prime lengths). Or $$\displaystyle L = \{ w \mid |w| \text{ is prime} \} $$ over $\{a,b\}$. But simpler: $$\displaystyle L = \{ a^n b^n \} $$ is not regular (proven by pumping lemma). So in exam, they often ask for $$\displaystyle \{a^n b^n\} $$ or $$\displaystyle \{a^n b^n c^n\} $$ (the latter is not CFL). For regular pumping, use $$\displaystyle \{a^n b^n\} $$.

  • Actually, $$\displaystyle \{a^n b^n\} $$ is not regular, so pumping lemma applies. Choose $$\displaystyle s = a^p b^p $$. Then $y$ consists only of a's (since $|xy|\leq p$). Pump down: $$\displaystyle xy^0z = a^{p-|y|} b^p $$. Since $$\displaystyle |y|>0 $$, number of a's < number of b's, so not in $L$. Contradiction.

• [!TIP] Pumping Lemma Pitfall: The lemma says "there exists $p$", so you choose $s$ based on that $p$. You must consider all possible $x,y,z$ decompositions satisfying the conditions. Often $y$ lies entirely in the first $p$ symbols.

III. CONTEXT-FREE LANGUAGES & GRAMMARS (CFG)

Context-Free Grammar (CFG)

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

  • $V$: finite set of variables/non-terminals.

  • $T$: finite set of terminals (alphabet).

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

  • $S \in V$: start variable.

• Derivations:

  • Leftmost derivation: At each step, replace the leftmost variable.

  • Rightmost derivation: At each step, replace the rightmost variable.

• Parse Tree (Derivation Tree):

  • Root labeled $S$.

  • Each interior node labeled with a variable $A$, children correspond to symbols in RHS of production $$\displaystyle A \rightarrow \alpha $$.

  • Leaves labeled with terminals or $\epsilon$.

  • Yield (concatenation of leaves left-to-right) is the derived string.

• [!TIP] Exam Tip: For a given string, multiple parse trees imply ambiguity. Always check if leftmost and rightmost derivations are unique for that string.

Ambiguity in CFG

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

• Example: The classic if-else grammar:

  
  S → if S else S | if S | other
  
  

  String if a if b else c has two parse trees.

  Given grammar: $$\displaystyle S \rightarrow aAB,\; A \rightarrow bC | cd,\; B \rightarrow c | d,\; C \rightarrow cd $$.

  String acdc? Check: $$\displaystyle S \Rightarrow aAB \Rightarrow a bC B \Rightarrow a b cd B \Rightarrow a b cd c $$? That gives abcdc. Not acdc. Actually, acdc: $$\displaystyle S \Rightarrow aAB \Rightarrow a A d \Rightarrow a bC d \Rightarrow a b cd d $$? No. Let's find a string with two derivations. Possibly acdc? From $$\displaystyle S \rightarrow aAB $$, if $$\displaystyle A \rightarrow cd $$, $$\displaystyle B \rightarrow c $$, gives acdc. If $$\displaystyle A \rightarrow bC $$, $$\displaystyle B \rightarrow d $$, then $S \Rightarrow a bC d \Rightarrow a b cd d$? That's abcdd. Not same. So maybe no ambiguity? But exam asks to check. Better example: $$\displaystyle S \rightarrow S+S | 0|1 $$. String 0+1+0 has two parse trees. For given grammar, we need to find a string with two leftmost derivations. Let's try acdc:

  Leftmost: $S \Rightarrow aAB \Rightarrow a cd B \Rightarrow a cd c$ (since $$\displaystyle B \rightarrow c $$).

  Another: $$\displaystyle S \Rightarrow aAB \Rightarrow a bC B \Rightarrow a b cd B \Rightarrow a b cd d $$? Not acdc. So maybe acdc only has one. Try abcdc: $$\displaystyle S \Rightarrow aAB \Rightarrow a bC B \Rightarrow a b cd B \Rightarrow a b cd c $$. That's one. Another? $$\displaystyle S \Rightarrow aAB \Rightarrow a A d \Rightarrow a bC d \Rightarrow a b cd d $$? That's abcdd. So no. Perhaps the grammar is unambiguous? But exam likely expects to show it's ambiguous by finding a string with two derivations. Maybe acdc is not generated? Let's generate all strings:

  $$\displaystyle S \rightarrow aAB $$.

  $$\displaystyle A \rightarrow bC $$ yields b cd, so a b cd B.

  $$\displaystyle A \rightarrow cd $$ yields cd, so a cd B.

  $$\displaystyle B \rightarrow c $$ or d.

  So strings: abcdc, abcdd, acdc, acdd.

  Now acdc: from a cd B with $$\displaystyle B \rightarrow c $$. Only one leftmost derivation? Leftmost: first replace $A$? Actually, leftmost derivation: start with $S$, replace $S$ with aAB (only choice). Then leftmost variable is $A$. Replace $A$ with cd (or bC). If replace with cd, then string becomes a cd B. Then leftmost variable is $B$, replace with c. So acdc. If we first replace $A$ with bC, then string a bC B. Then leftmost variable is $$\displaystyle bC`? Actually, `bC` is not a single variable; after replacing $$A$$\displaystyle with `bC`, the string is `a b C B`. Leftmost variable is `C`? No, leftmost variable is the first variable from left: `C`? Actually, the string is `a b C B`. Variables are `C` and `B`. Leftmost is `C`. Replace `C` with `cd`: `a b cd B`. Then leftmost variable is `B`, replace with `c`: `a b cd c` = `abcdc`. So `acdc` only from choosing $$A \rightarrow cd$$\displaystyle . So unique. So maybe the grammar is unambiguous. But the exam question says "check whether the grammar is ambiguous". So we need to check all strings. Possibly it is unambiguous. But typical exam examples are ambiguous. Perhaps I misread: $$A \rightarrow bC / cd$ means $A \rightarrow bC$ or $A \rightarrow cd$. $B \rightarrow c / d$$\displaystyle . So as above. So for string acdc, only one leftmost derivation. So unambiguous. But maybe there is another string? acdd: from a cd B with $$B \rightarrow d$. Unique. `abcdc`: from `a bC B` with $C \rightarrow cd$, $B \rightarrow c$. Unique. `abcdd`: from `a bC B` with $C \rightarrow cd$, $B \rightarrow d$. Unique. So no ambiguity. So answer: grammar is unambiguous. But exam might expect to show it's ambiguous by finding a string with two parse trees. Perhaps they meant a different grammar. Anyway, in notes, define ambiguity and give classic example like `S → aSbS | bSaS | ε` or `S → S+S | 0|1`. * **Methods to Remove Ambiguity**: * **Left-factoring**: Factor common prefixes. Example: $$\displaystyle S \rightarrow aA | aB $$ becomes $$\displaystyle S \rightarrow aS' $$, $$\displaystyle S' \rightarrow A | B $$. * **Grammar transformation**: Rewrite to enforce a unique parse (e.g., for arithmetic expressions, enforce precedence and associativity). * **Inherently ambiguous languages**: Some CFLs have only ambiguous grammars (e.g., $$\displaystyle {a^i b^j c^k \mid i=j \text{ or } j=k} $$). No unambiguous CFG exists.

Normal Forms

• Chomsky Normal Form (CNF):

  • Productions are of the form:

    • $$\displaystyle A \rightarrow BC $$ (both variables)

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

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

  • Conversion Procedure:

    1. Eliminate $\epsilon$-productions (except possibly $$\displaystyle S \rightarrow \epsilon $$): For each nullable variable $A$ (that can derive $\epsilon$), add productions with $A$ omitted in all combinations. Remove $$\displaystyle A \rightarrow \epsilon $$ if $A \neq S$.

    2. Eliminate unit productions ($$\displaystyle A \rightarrow B $$): For each $$\displaystyle A \rightarrow B $$, add $$\displaystyle A \rightarrow \alpha $$ for all $$\displaystyle B \Rightarrow^+ \alpha $$ where $\alpha$ is not a single variable.

    3. Eliminate useless symbols: Remove non-generating and non-reachable variables.

    4. Convert to binary: For productions $$\displaystyle A \rightarrow \alpha $$ with $|\alpha| \geq 3$, introduce new variables to break $\alpha$ into binary form: $$\displaystyle A \rightarrow B \alpha' $$, where $B$ is first symbol of $\alpha$, $\alpha'$ is rest.

  • Example: Convert $$\displaystyle S \rightarrow aSb | ab $$.

    • No $\epsilon$, no unit, all useful. Already in CNF? $aSb$ has three symbols: $$\displaystyle S \rightarrow a S b $$. Not binary. Convert: introduce $$\displaystyle A \rightarrow S b $$, then $$\displaystyle S \rightarrow a A $$, $$\displaystyle A \rightarrow S b $$. But $$\displaystyle A \rightarrow S b $$ is not CNF because $S b$ is variable+terminal. Need all terminals alone. So better: $$\displaystyle S \rightarrow a S b $$ → introduce $$\displaystyle B \rightarrow S b $$? Then $$\displaystyle S \rightarrow a B $$, $$\displaystyle B \rightarrow S b $$. But $$\displaystyle B \rightarrow S b $$ still has terminal. Actually, in CNF, RHS must be either two variables or one terminal. So $$\displaystyle S \rightarrow a S b $$ is not allowed. We need to replace terminals with variables: introduce $$\displaystyle A \rightarrow a $$, $$\displaystyle B \rightarrow b $$. Then $$\displaystyle S \rightarrow A S B $$. That's CNF: $$\displaystyle A \rightarrow a $$, $$\displaystyle B \rightarrow b $$, $$\displaystyle S \rightarrow A S B $$. But $$\displaystyle S \rightarrow A S B $$ has three variables. Need binary: introduce $$\displaystyle C \rightarrow S B $$, then $$\displaystyle S \rightarrow A C $$, $$\displaystyle C \rightarrow S B $$. Now all productions: $$\displaystyle A \rightarrow a $$, $$\displaystyle B \rightarrow b $$, $$\displaystyle S \rightarrow A C $$, $$\displaystyle C \rightarrow S B $$. That's CNF.

• Greibach Normal Form (GNF):

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

  • Conversion Procedure (high-level):

    1. Ensure start variable does not appear on RHS.

    2. Order variables $$\displaystyle A_1, A_2, ..., A_n $$.

    3. For each $$\displaystyle A_i $$ in order, eliminate productions with variables of higher index on RHS by substitution.

    4. Eliminate left recursion.

    5. Convert remaining to GNF by ensuring RHS starts with terminal.

  • Example: $$\displaystyle S \rightarrow aSb | ab $$.

    • Already, $$\displaystyle S \rightarrow aSb $$ starts with a, but has S after. That's allowed in GNF? Yes, GNF allows $$\displaystyle A \rightarrow a \alpha $$ where $\alpha$ is any string of variables. So $$\displaystyle S \rightarrow a S b $$ is in GNF? But b is terminal, not variable. So $\alpha$ must be all variables. Here $$\displaystyle \alpha = S b $$ contains terminal b. So not GNF. Need to replace b with a variable: introduce $$\displaystyle B \rightarrow b $$. Then $$\displaystyle S \rightarrow a S B $$. That's GNF: $$\displaystyle S \rightarrow a S B $$, $$\displaystyle B \rightarrow b $$. Also $$\displaystyle S \rightarrow a b $$ becomes $$\displaystyle S \rightarrow a B $$. So final: $$\displaystyle S \rightarrow a S B | a B $$, $$\displaystyle B \rightarrow b $$.

• [!TIP] CNF vs GNF: CNF is used for CYK parsing algorithm and proving properties. GNF is used for constructing PDAs (since GNF grammar directly gives NPDA with one transition per production).

Properties of CFLs

• Closure Properties:

  • Closed under: Union, Concatenation, Kleene Star.

  • Not closed under: Intersection, Complement, Difference.

    • Proof: $$\displaystyle \{a^n b^n c^n\} $$ is not CFL but is intersection of $$\displaystyle \{a^n b^n c^*\} $$ and $$\displaystyle \{a^* b^n c^n\} $$, both CFLs.

• Pumping Lemma for CFLs:

  • Statement: If $L$ is CFL, then $\exists p \geq 0$ such that $\forall s \in L$ with $|s| \geq p$, $s$ can be written $$\displaystyle s = uvwxy $$ with:

    1. $|vwx| \leq p$

    2. $|vx| \geq 1$

    3. $$\displaystyle \forall i \geq 0, u v^i w x^i y \in L $$

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

    • Choose $$\displaystyle s = a^p b^p c^p $$.

    • Cases based on where $vwx$ lies. In all cases, pumping $$\displaystyle i=0 $$ or $$\displaystyle i=2 $$ breaks balance of counts.

CFG Construction

• Design CFGs for specific patterns:

  • $$\displaystyle \{a^m b^n c^{2m} d^n \mid m>0, n \geq 0\} $$:

    
    S → a S c c | a T
    
    T → b T d | ε
    
    

  • Regular expression $$\displaystyle (011+1)^*(01)^* $$: Convert RE to CFG by treating each operator as a production.

    
    S → A B
    
    A → 011 A | 1 A | ε
    
    B → 01 B | ε
    
    

  • Palindromes: $$\displaystyle S \rightarrow a S a | b S b | a | b | \epsilon $$.

  • $$\displaystyle w c w^R $$: $$\displaystyle S \rightarrow c | a S a | b S b $$.

IV. PUSHDOWN AUTOMATA (PDA)

Definition & Model

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

  • $Q$: finite states.

  • $\Sigma$: input alphabet.

  • $\Gamma$: stack alphabet.

  • $$\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$: set of final states (for acceptance by final state).

• Instantaneous Description (ID): $(q, w, \gamma)$ where $q$ is current state, $w$ is unread input, $\gamma$ is stack content (top on left).

• Transition: $$\displaystyle (q, a, A) \rightarrow (p, \beta) $$ means in state $q$, reading $a$ (or $\epsilon$) with $A$ on top, go to state $p$, replace $A$ with $\beta$ (push $\beta$; if $$\displaystyle \beta = \epsilon $$, pop $A$).

Types & Acceptance

• Non-deterministic PDA (NPDA): $\delta$ can have multiple choices. More powerful.

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

• Acceptance by Final State: $w \in L(M)$ if there exists a sequence of moves from $$\displaystyle (q_0, w, Z_0) $$ to $(q, \epsilon, \gamma)$ with $q \in F$ (stack can be non-empty).

• Acceptance by Empty Stack: $w \in N(M)$ if there exists a sequence from $$\displaystyle (q_0, w, Z_0) $$ to $(q, \epsilon, \epsilon)$ for some $q$ (no final states needed).

• Equivalence: For any PDA, we can construct another that accepts the same language by empty stack (remove final states, add new start state and transitions to empty stack) or by final state (add new final state and $\epsilon$-transitions from all states to it when stack empty). But DPDA languages are a proper subset of NPDA languages (e.g., $$\displaystyle \{a^i b^j c^k \mid i=j \text{ or } j=k\} $$ is NPDA but not DPDA).

PDA Construction

• Design Principles:

  • Use stack to store unmatched symbols (e.g., for $$\displaystyle a^n b^n $$, push a's, pop on b's).

  • For palindromes $$\displaystyle ww^R $$, push first half, then pop and match second half (non-deterministic guess midpoint).

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

• Examples:

  • $$\displaystyle L = \{a^n b^n \mid n \geq 1\} $$ by final state:

    
    δ(q0, a, Z0) = (q0, AZ0)   // push A for each a
    
    δ(q0, a, A) = (q0, AA)
    
    δ(q0, b, A) = (q1, ε)      // pop A on b
    
    δ(q1, b, A) = (q1, ε)
    
    δ(q1, ε, Z0) = (q2, ε)     // accept when stack only Z0
    
    

    Final state $$\displaystyle q_2 $$.

  • $$\displaystyle L = \{w w^R \mid w \in \{a,b\}^*\} $$ by empty stack:

    
    δ(q0, a, Z0) = (q0, aZ0)
    
    δ(q0, b, Z0) = (q0, bZ0)
    
    δ(q0, a, a) = (q0, aa)
    
    δ(q0, b, b) = (q0, bb)
    
    δ(q0, a, b) = (q1, ε)   // non-deterministic: guess midpoint, start popping
    
    δ(q0, b, a) = (q1, ε)
    
    δ(q0, ε, Z0) = (q2, ε)  // accept empty string
    
    δ(q1, a, a) = (q1, ε)
    
    δ(q1, b, b) = (q1, ε)
    
    δ(q1, ε, Z0) = (q2, ε)
    
    

    Accept by empty stack (state $$\displaystyle q_2 $$ not necessary if we allow $(q1, \epsilon, \epsilon)$).

  • Even-length palindromes: Similar to above, but must ensure even length. Can push two symbols at a time or use two states to track parity.

CFG ↔ PDA Conversion

• CFG to PDA (by empty stack):

  1. PDA has one state $q$.

  2. Initial stack symbol is start variable $S$.

  3. For each production $$\displaystyle A \rightarrow \alpha $$, add transition $\delta(q, \epsilon, A) \ni (q, \alpha)$ (push $\alpha$).

  4. For each terminal $a$, add $\delta(q, a, a) \ni (q, \epsilon)$ (match and pop).

  5. Accept by empty stack.

  • This PDA simulates leftmost derivations: stack holds current sentential form.

• PDA to CFG:

  1. For each pair of states $p, q \in Q$, create a variable $$\displaystyle A_{pq} $$ representing "the set of strings that take PDA from state $p$ with empty stack to state $q$ with empty stack".

  2. Add productions:

     • $$\displaystyle A_{pq} \rightarrow a A_{rs} b $$ if $$\displaystyle \delta(p,a,A) \ni (r, B_1...B_k...) $$? Actually, standard construction: For each transition $$\displaystyle (p, a, A) \rightarrow (r, \gamma) $$ where $$\displaystyle \gamma = B_1 B_2 ... B_m $$, and for any sequence of states $$\displaystyle r = r_0, r_1, ..., r_m = q $$, add $$\displaystyle A_{pq} \rightarrow a A_{r_0 r_1} A_{r_1 r_2} ... A_{r_{m-1} r_m} b $$? This is complex. Simplified: if $\delta(p, a, A) \ni (r, BC)$, then $$\displaystyle A_{pq} \rightarrow a A_{rq} B_{?} $$? Actually, the standard method: For each transition $$\displaystyle (p, a, A) \rightarrow (r, \epsilon) $$, add $$\displaystyle A_{pq} \rightarrow a $$ if $$\displaystyle r=q $$. For $$\displaystyle (p, a, A) \rightarrow (r, BC) $$, add $$\displaystyle A_{pq} \rightarrow a A_{r k} B_{k q} $$ for all $k$. But easier: use the construction where variables are $[p, A, q]$ meaning "from state $p$ with $A$ on stack to state $q$ with $A$ popped". Then productions derived from transitions.

  3. Start variable is $$\displaystyle A_{q_0 Z_0 q} $$ for some $q$? Actually, for acceptance by empty stack, we want strings that take from $$\displaystyle (q_0, w, Z_0) $$ to $(q, \epsilon, \epsilon)$. So variable $$\displaystyle A_{q_0 Z_0 q} $$ for any $q$. But typically we add a new start variable $S$ with $$\displaystyle S \rightarrow A_{q_0 Z_0 q} $$ for all $q$.

  • Example: Given PDA with transitions:

    
    δ(q0, 1, S) = (q0, AS)
    
    δ(q0, ε, S) = (q0, ε)
    
    δ(q0, 1, A) = (q0, AA)
    
    δ(q0, 0, A) = (q1, A)
    
    δ(q1, 0, S) = (q0, S)
    
    

    Construct CFG. Variables: $$\displaystyle [q_i, X, q_j] $$ for states $$\displaystyle q_i, q_j $$ and stack symbol $X$.

    Transitions:

    1. $$\displaystyle (q0, 1, S) \rightarrow (q0, AS) $$: So $$\displaystyle [q0, S, q_j] $$ can produce $$\displaystyle 1 [q0, A, q_k] [q_k, S, q_j] $$ for any $k$.

    2. $$\displaystyle (q0, ε, S) \rightarrow (q0, ε) $$: $$\displaystyle [q0, S, q0] \rightarrow ε $$.

    3. $$\displaystyle (q0, 1, A) \rightarrow (q0, AA) $$: $$\displaystyle [q0, A, q_j] \rightarrow 1 [q0, A, q_k] [q_k, A, q_j] $$.

    4. $$\displaystyle (q0, 0, A) \rightarrow (q1, A) $$: $$\displaystyle [q0, A, q_j] \rightarrow 0 [q1, A, q_j] $$.

    5. $$\displaystyle (q1, 0, S) \rightarrow (q0, S) $$: $$\displaystyle [q1, S, q_j] \rightarrow 0 [q0, S, q_j] $$.

    Start variable: Since PDA accepts by empty stack? Not specified. Usually for conversion, assume acceptance by empty stack. Then we want strings that take from $(q0, w, S)$ to $(q, \epsilon, \epsilon)$. So we need $[q0, S, q]$ for any $q$? Actually, to empty stack, we need to pop $S$ and end with empty stack. So $[q0, S, q]$ means from state $q0$ with $S$ on top to state $q$ with $S$ popped. But after popping $S$, stack might have other symbols? In the construction, $[p, A, q]$ means: starting with $A$ on top, after some moves, $A$ is popped and we are in state $q$, with whatever was below $A$ now on top? Actually, the standard construction ensures that the variable $[p, A, q]$ generates exactly the strings that take the PDA from state $p$ with $A$ on the stack to state $q$ with $A$ removed (and stack below unchanged). So for acceptance by empty stack, we start with $S$ on stack and want to end with empty stack. So we need to pop $S$ and have no other symbols. That corresponds to $[q0, S, q]$ for some $q$, but after popping $S$, the stack should be empty. That means that below $S$ there was nothing, so $S$ was the only symbol. So we need $[q0, S, q]$ where the transition that pops $S$ leaves the stack empty. In the construction, that happens when the transition for $S$ is $$\displaystyle (p, a, S) \rightarrow (r, \epsilon) $$. Then $$\displaystyle [p, S, r] \rightarrow a $$. So in our case, we have $$\displaystyle (q0, ε, S) \rightarrow (q0, ε) $$, so $$\displaystyle [q0, S, q0] \rightarrow ε $$. So $$\displaystyle S_{start} \rightarrow [q0, S, q0] $$. Then we can derive other variables. But also we have other transitions that push. So the grammar will generate all strings that lead to empty stack. This is complex for an exam. Usually they give a simple PDA and ask for CFG. In such cases, we can reason directly: The PDA seems to generate strings of 1's and 0's? From transitions: from $q0$, on 1 we push A or AS? Actually, $$\displaystyle \delta(q0,1,S)=(q0,AS) $$: so on reading 1 with S on top, push AS (so S becomes below A). Then $$\displaystyle \delta(q0,1,A)=(q0,AA) $$: on 1 with A, push AA. $$\displaystyle \delta(q0,0,A)=(q1,A) $$: on 0 with A, go to q1, keep A. $$\displaystyle \delta(q1,0,S)=(q0,S) $$: on 0 with S, go to q0. And $$\displaystyle \delta(q0,ε,S)=(q0,ε) $$: can pop S without reading. So this PDA likely accepts language of strings with equal number of 1's and 0's? Not sure. But for exam, they expect the systematic method.

• [!TIP] CFG↔PDA Tip: CFG→PDA is straightforward (one state, push/pop). PDA→CFG is more involved; focus on the idea that each variable corresponds to a "stack operation" between two states.

V. TURING MACHINES (TM) & COMPUTABILITY

Turing Machine Definition

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

  • $Q$: finite states.

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

  • $\Gamma$: tape alphabet, $\Sigma \subseteq \Gamma$, $B \in \Gamma$.

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

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

  • $B$: blank symbol.

  • $F \subseteq Q$: final states.

• Instantaneous Description (ID): $(q, u, a, v)$ where tape = $u a v$, head scans $a$, state $q$, $u$ and $v$ are left and right of head.

• Transition: $$\displaystyle \delta(q, a) = (r, b, D) $$ means in state $q$ reading $a$, write $b$, move head $D \in \{L,R\}$, go to state $r$.

• Acceptance: $w \in L(M)$ if starting from $$\displaystyle (q_0, \epsilon, w) $$ (with head at leftmost symbol), there is a sequence leading to a state in $F$ (TM may not halt on rejection).

TM Construction Techniques

• Storing Information: Use multiple tracks on tape (e.g., separate sections for input, markers, scratch).

• Marking and Crossing Off: Change symbol to a marker (e.g., X) to indicate it has been processed. For $$\displaystyle a^n b^n $$, repeatedly mark leftmost a and rightmost b.

• Simulating Other Machines: For DFA, TM can just follow transitions without writing. For PDA, simulate stack with tape.

• Handling Multiple Tracks: Use a larger tape alphabet: each cell contains tuple $$\displaystyle (symbol_1, symbol_2, ...) $$.

• Semi-infinite Tape: Assume left-end marker $\vdash$; head never goes left of it.

TM Variants

• Multi-tape TM: Has $k$ tapes, each with its own head. Transition: $$\displaystyle \delta: Q \times \Gamma^k \rightarrow Q \times \Gamma^k \times \{L,R,S\}^k $$.

• Non-deterministic TM: $$\displaystyle \delta: Q \times \Gamma \rightarrow P(Q \times \Gamma \times \{L,R\}) $$.

• Equivalence: Any multi-tape TM can be simulated by a single-tape TM (use multiple tracks and separators). Any non-deterministic TM can be simulated by a deterministic TM (breadth-first search of computation tree). Thus, all variants have the same computational power (recognize RE languages).

TM Design Examples

• Even number of 1's: Two states: $$\displaystyle q_{even} $$ (start, final), $$\displaystyle q_{odd} $$. On reading 1, toggle state. Ignore 0's.

• $$\displaystyle a^n b^n c^n $$:

  1. Mark first a as X.

  2. Scan right to find first b, mark as Y.

  3. Scan right to find first c, mark as Z.

  4. Repeat until all a,b,c marked. If any a,b,c left unmatched, reject.

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

  1. Mark first symbol of $W$ (say 0 as X).

  2. Scan right to C, then to end, find matching symbol (if X then 0), mark as X.

  3. Repeat for next symbol of $W$.

  4. Accept if all symbols of $W$ matched and no extra symbols.

• Binary multiple of 3:

  • States represent current remainder mod 3: $$\displaystyle q_0 $$ (0), $$\displaystyle q_1 $$ (1), $$\displaystyle q_2 $$ (2).

  • Start at $$\displaystyle q_0 $$.

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

  • Accept if final state $$\displaystyle q_0 $$ after reading all input.

• Multiplication of two numbers (unary or binary? Usually unary for simplicity):

  • Input: $$\displaystyle a^n \# a^m $$ (unary).

  • Algorithm: Repeatedly add $$\displaystyle a^m $$ to result $n$ times. Use markers to count.

  • Steps: Copy second number after #, then repeatedly: mark one a in first number, add one copy of second number to result area, until all a's in first are marked. Then erase markers and first number, leave result.

Universal Turing Machine (UTM)

• Concept: A TM $U$ that takes as input a description of an arbitrary TM $M$ (encoded as a string) and an input string $w$, and simulates $M$ on $w$.

• Significance: Foundation of the stored-program computer. Shows that a single machine can perform any computation by interpreting a program. Implies existence of a universal language that is RE but not recursive (by diagonalization).

VI. DECIDABILITY, UNDECIDABILITY & COMPLEXITY

Language Classes

• Recursive (Decidable): $L$ is recursive if $\exists$ a TM that halts on all inputs and accepts exactly $L$.

• Recursively Enumerable (RE): $L$ is RE if $\exists$ a TM that accepts every string in $L$ (halts in accept state), and for strings not in $L$, it may reject or loop.

• Relationship: Every recursive language is RE, but not conversely. There exist RE languages that are not recursive (e.g., the Halting Problem language $$\displaystyle H_{TM} $$).

• Co-RE: Complement of an RE language. Not all RE languages are co-RE.

Undecidable Problems

• Halting Problem:

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

  • Proof by Contradiction: Assume decider $H$ for $$\displaystyle HALT_{TM} $$ exists. Construct a TM $D$ that on input $\langle M \rangle$:

    1. Run $H(\langle M, \langle M \rangle \rangle)$.

    2. If $H$ accepts (i.e., $M$ halts on its own description), then loop.

    3. If $H$ rejects, then halt.

    Then consider $D(\langle D \rangle)$: if $D$ halts on itself, then by definition it should loop; if it loops, it should halt. Contradiction. Hence $$\displaystyle HALT_{TM} $$ undecidable.

  • Consequence: No algorithm can determine if an arbitrary program halts on a given input.

• Post Correspondence Problem (PCP):

  • Definition: Given a set of dominoes $$\displaystyle \{(x_1, y_1), (x_2, y_2), ..., (x_k, y_k)\} $$ where $$\displaystyle x_i, y_i $$ are strings over an alphabet $\Sigma$, does there exist a sequence of indices $$\displaystyle i_1, i_2, ..., i_m $$ (with repetition allowed) such that $$\displaystyle x_{i_1} x_{i_2} ... x_{i_m} = y_{i_1} y_{i_2} ... y_{i_m} $$?

  • Example: $\{(b, bab), (a, ab), (ba, a), (bb, b)\}$. Solution: b a b a b b? Check: top: b a b a b b = bababb; bottom: bab a b b = bababb. Yes.

  • Undecidability: Proven by reduction from the acceptance problem for TMs. If we could solve PCP, we could solve $$\displaystyle A_{TM} $$.

Complexity Classes

• P: Set of languages decidable by a deterministic TM in polynomial time ($$\displaystyle O(n^k) $$ for some $k$). "Efficiently solvable."

• NP: Set of languages for which there exists a non-deterministic TM that decides in polynomial time, or equivalently, languages for which "yes" instances have polynomial-size certificates verifiable in polynomial time by a deterministic TM.

  • Example: SAT (satisfiability of Boolean formula). Given assignment (certificate), verify in poly-time.

• NP-complete:

  • A language $L$ is NP-complete if:

    1. $L \in \text{NP}$.

    2. Every language in NP reduces to $L$ in polynomial time (i.e., $L$ is NP-hard).

  • Significance: If any NP-complete problem has a polynomial-time algorithm, then P = NP.

  • Examples: 3-SAT, Clique, Vertex Cover, Hamiltonian Cycle, Subset Sum.

• Reducibility: Many-one reduction ($$\displaystyle \leq_m $$): $$\displaystyle L_1 \leq_m L_2 $$ if $\exists$ a computable function $f$ in polynomial time such that $$\displaystyle x \in L_1 \iff f(x) \in L_2 $$. Used to prove NP-hardness (reduce known NP-complete problem to $L$) and undecidability (reduce $$\displaystyle HALT_{TM} $$ to $L$).

VII. ADVANCED TOPICS & THEORETICAL FRAMEWORKS

Chomsky Hierarchy

• Type 0 (Unrestricted): Grammars with no restrictions. Equivalent to Turing Machines. Languages = Recursively Enumerable (RE).

• Type 1 (Context-sensitive): Productions $$\displaystyle \alpha A \beta \rightarrow \alpha \gamma \beta $$ with $|\gamma| \geq 1$. Equivalent to Linear-Bounded Automaton (LBA). Languages = Context-Sensitive Languages (CSL). All recursive languages are CSL, but not all CSL are recursive? Actually, CSL = recursive? It is known that CSL = NSPACE(O(n)) and by Savitch's theorem, they are closed under complement, so CSL = recursive? Wait: CSL are exactly the languages accepted by LBAs. It is known that every LBA halts on all inputs? Not necessarily; LBA is non-deterministic and may loop. But the class of languages accepted by LBAs (acceptance by final state) is exactly the class of context-sensitive languages, and it is known that CSL = NSPACE(O(n)) and by Immerman–Szelepcsényi theorem, NSPACE(O(n)) is closed under complement, so CSL are decidable? Actually, an LBA always halts because its tape is bounded by input length, so the configuration space is finite, so it must halt or loop? But since configuration space is finite, if it loops, it will repeat a configuration and can be detected. So an LBA can be made to halt on all inputs? Not necessarily; but the language accepted by an LBA (by final state) is decidable because we can simulate all possible paths up to the number of configurations. So CSL ⊆ recursive. And it is known that every recursive language is CSL? Not all recursive languages are context-sensitive? Actually, there are recursive languages that are not context-sensitive? The hierarchy: regular ⊂ CFL ⊂ CSL ⊂ recursive? But it is known that CSL = recursive? No, CSL is a proper subset of recursive? Actually, by space hierarchy theorem, there are recursive languages not in NSPACE(O(n)). So CSL ⊂ recursive. But it is known that every context-sensitive language is decidable (since LBA halts). So CSL ⊆ recursive. And there are recursive languages not context-sensitive. So hierarchy: Type 3 ⊂ Type 2 ⊂ Type 1 ⊂ Type 0, with Type 1 ⊂ recursive ⊂ RE.

• Type 2 (Context-free): Productions $$\displaystyle A \rightarrow \gamma $$. Equivalent to Pushdown Automaton. Languages = CFL.

• Type 3 (Regular): Productions $$\displaystyle A \rightarrow aB $$ or $$\displaystyle A \rightarrow a $$ (right-linear) or left-linear. Equivalent to Finite Automaton. Languages = Regular.

• Inclusions: Regular ⊂ CFL ⊂ CSL ⊂ RE. All inclusions are proper.

Petri Nets Model

• Basic Components:

  • Places (circles): Represent conditions or resources.

  • Transitions (rectangles): Represent events that may occur.

  • Tokens (dots): Represent the presence of resources.

  • Arcs: Connect places to transitions and transitions to places. Weighted arcs (usually 1) indicate how many tokens are consumed/produced.

• Firing Rule: A transition is enabled if each input place has at least as many tokens as the arc weight. When it fires, it consumes tokens from input places and produces tokens in output places.

• Reachability: A marking (distribution of tokens) $M'$ is reachable from $M$ if there is a sequence of firings leading from $M$ to $M'$.

• Applications: Modeling concurrent systems, distributed algorithms, workflow systems, communication protocols. Analysis of properties like liveness, boundedness, reachability is decidable? Actually, reachability problem for Petri nets is decidable (Mayr algorithm), but complex.

Additional Short Note Topics (from past papers)

• Two-way Finite Automata (2-DFA): Can move head left/right. Same power as 1-DFA (recognize regular languages), but can be exponentially more succinct. Acceptance: head must be at right end marker in final state.

• Properties of Context-Free Grammars:

  • Closure: Union, concatenation, Kleene star, substitution, reversal, intersection with regular.

  • Non-closure: Intersection, complement, difference.

  • Inherent Ambiguity: Some CFLs have no unambiguous grammar (e.g., $$\displaystyle \{a^i b^j c^k \mid i=j \text{ or } j=k\} $$).

  • Decision Problems: Emptiness, finiteness, membership (CYK algorithm) are decidable. Ambiguity is undecidable.

• Mathematical Induction: Used extensively in proofs (e.g., correctness of subset construction, pumping lemma). Principle: If $P(0)$ true and $P(k) \Rightarrow P(k+1)$, then $P(n)$ for all $n$.

• NFA Properties: Equivalent to DFA (same language class). Subset construction may cause exponential blowup. ε-NFA equivalent to NFA.

• Closure Properties of Regular Languages (revisited): Already covered, but emphasize constructions.

• P vs NP: P = problems solvable in poly-time; NP = problems verifiable in poly-time. P ⊆ NP. Whether P = NP is open. NP-complete problems are hardest in NP.

• Petri Nets (already covered).

• Halting Problem (already covered).

• Chomsky Hierarchy (already covered).

Final Summary Table: Key Equivalences

[!CAUTION] Exam Warning:

• In DFA minimization, ensure you mark all distinguishable pairs correctly; missing a pair leads to over-merging.

• For CNF conversion, order matters: eliminate ε-productions first, then unit productions, then useless symbols, then convert to binary.

• In PDA design, clearly state acceptance mode (final state or empty stack) and ensure stack operations match the language pattern.

• For TM designs, provide clear step-by-step description with tape markings and state transitions; use high-level intuition first.

• When proving undecidability, use reduction from a known undecidable problem (e.g., $$\displaystyle A_{TM} $$ or $$\displaystyle HALT_{TM} $$) and construct a computable transformation.

• For pumping lemma proofs, choose the pumping length $p$ and a specific string $s$ that forces $y$ to be in a critical region; consider all cases for the location of $y$.