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

I. FINITE AUTOMATA (FA)

A. 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$: input alphabet

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

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

  • $F \subseteq Q$: set of accept states

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

• State diagram: Circles for states, arrows labeled with input symbols, double circle for final states.

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

• Design examples:

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

    • States: $$\displaystyle q_0 $$ (start), $$\displaystyle q_1 $$ (saw 1), $$\displaystyle q_2 $$ (saw 1 and last 0), $$\displaystyle q_d $$ (dead).

    • Transitions: $$\displaystyle \delta(q_0,0)=q_d $$, $$\displaystyle \delta(q_0,1)=q_1 $$, $$\displaystyle \delta(q_1,0)=q_2 $$, $$\displaystyle \delta(q_1,1)=q_1 $$, $$\displaystyle \delta(q_2,0)=q_2 $$, $$\displaystyle \delta(q_2,1)=q_1 $$, $$\displaystyle \delta(q_d,0)=\delta(q_d,1)=q_d $$.

    • Final state: $$\displaystyle q_2 $$.

  • Exactly two a's and two b's over $\{a,b\}$:

    • States represent counts $$\displaystyle (c_a, c_b) $$ where $$\displaystyle 0 \leq c_a, c_b \leq 2 $$, plus dead state.

    • Start: $(0,0)$. On a, increase $$\displaystyle c_a $$ if $$\displaystyle <2 $$, else go to dead; similarly for b.

    • Final state: $(2,2)$.

  • Residue mod $m$ (binary input):

    • States: $0,1,\dots,m-1$ representing remainder.

    • Transition: $$\displaystyle \delta(r, b) = (2r + b) \bmod m $$.

    • Start: $0$. Accept if remainder $0$ (or output remainder in Mealy/Moore).

[!TIP] For DFA design, identify what needs to be remembered (e.g., last symbol, count modulo $m$) and create states accordingly. Always include a dead state for invalid transitions.

B. Non-deterministic Finite Automata (NFA)

• Definition: Similar to DFA but $$\displaystyle \delta: Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q) $$. Allows multiple transitions for same input and $\varepsilon$-transitions.

• Differences from DFA:

  • NFA can be in multiple states simultaneously.

  • DFA has exactly one transition per state-input pair.

  • Every DFA is an NFA, but not vice versa.

• $\varepsilon$-NFA: NFA with $\varepsilon$-transitions.

• Design example: Strings over $\{a,b\}$ containing neither aa nor bb:

  • States: $S$ (start), $A$ (last a), $B$ (last b).

  • Transitions: $$\displaystyle \delta(S,a)=\{A\} $$, $$\displaystyle \delta(S,b)=\{B\} $$, $$\displaystyle \delta(A,a)=\emptyset $$, $$\displaystyle \delta(A,b)=\{B\} $$, $$\displaystyle \delta(B,a)=\{A\} $$, $$\displaystyle \delta(B,b)=\emptyset $$.

  • Final states: $\{S,A,B\}$ (accepts empty string and all alternating strings).

C. Conversions and Equivalence

• Subset construction (NFA/$\varepsilon$-NFA to DFA):

  • DFA state = subset of NFA states.

  • Start state: $\varepsilon$-closure$$\displaystyle (q_0) $$.

  • Transition: $$\displaystyle \delta_{\text{DFA}}(S, a) = \varepsilon\text{-closure}\left( \bigcup_{q \in S} \delta_{\text{NFA}}(q, a) \right) $$.

• $\varepsilon$-closure: Set of states reachable from a state via $\varepsilon$-transitions (including itself).

• Equivalence proof: Every NFA has an equivalent DFA (subset construction). $\varepsilon$-NFA equivalent to NFA by removing $\varepsilon$-transitions via $\varepsilon$-closure.

[!TIP] In subset construction, the DFA may have up to $$\displaystyle 2^n $$ states for an $n$-state NFA. Always compute $\varepsilon$-closure for $\varepsilon$-NFA.

D. DFA Minimization

• Table-filling algorithm:

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

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

  3. Unmarked pairs are equivalent and can be merged.

• Myhill-Nerode theorem: The number of states in the minimal DFA equals the number of equivalence classes under the relation $$\displaystyle x \equiv_L y \iff \forall z \in \Sigma^*, xz \in L \Leftrightarrow yz \in L $$.

• Minimization: Merge equivalent states from table-filling.

[!TIP] Minimization reduces states but preserves language. Always check reachability before minimization (remove unreachable states first).

E. Finite Automata with Outputs

• Mealy machine: Output depends on current state and input. Components $$\displaystyle (Q, \Sigma, \Delta, \Gamma, \delta, \lambda, q_0) $$ where $\lambda: Q \times \Sigma \to \Delta$.

• Moore machine: Output depends only on current state. $\lambda: Q \to \Delta$.

• Conversion:

  • Mealy to Moore: Split each Mealy state into multiple Moore states based on output differences.

  • Moore to Mealy: Assign output of Moore state to all outgoing transitions.

• Design for residue mod $m$:

  • Mealy: On reading bit $b$, compute new remainder $$\displaystyle r' = (2r + b) \bmod m $$, output $r'$.

  • Moore: State represents remainder $r$, output $r$; transition as above.

II. REGULAR LANGUAGES AND EXPRESSIONS

A. Regular Expressions (RE)

• Definition: Built from $\emptyset$, $\varepsilon$, symbols in $\Sigma$ using operators: union ($+$), concatenation, Kleene star ($$\displaystyle ^* $$).

• Operators precedence: star > concatenation > union.

• Constructing RE:

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

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

  • $$\displaystyle a^x $$ divisible by 3 or 5: $$\displaystyle (a^3)^* + (a^5)^* $$.

• RE from DFA: State elimination method:

  1. Add new start and final states.

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

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

B. Arden’s Theorem

• Statement: For equations over RE, if $A$ does not contain $\varepsilon$, then $$\displaystyle X = AX + B $$ has unique solution $$\displaystyle X = A^*B $$.

• Solving systems:

  • Write equations for each state: $$\displaystyle q_i = \sum \delta(q_i, a) q_j + \text{initial/terminal terms} $$.

  • Solve by substitution, using Arden’s theorem.

• Applications: Converting automata to RE, especially for cyclic structures.

[!TIP] Arden’s theorem applies when the coefficient $A$ does not contain $\varepsilon$. For systems, solve in order of dependency.

C. Closure Properties of Regular Languages

Regular languages are closed under:

• Union: $$\displaystyle L_1 \cup L_2 $$ – product DFA with final states where either component is final.

• Intersection: $$\displaystyle L_1 \cap L_2 $$ – product DFA with final states where both components are final.

• Complement: $\overline{L}$ – swap final and non-final states in DFA.

• Concatenation: $$\displaystyle L_1L_2 $$ – $\varepsilon$-transitions from finals of $$\displaystyle M_1 $$ to start of $$\displaystyle M_2 $$.

• Kleene star: $$\displaystyle L^* $$ – add new start/final state with $\varepsilon$-transitions.

• Reversal: $$\displaystyle L^R $$ – reverse all transitions, swap start and finals.

[!TIP] Use product construction for intersection and union. For complement, ensure DFA is complete (add dead state if needed).

D. Pumping Lemma for Regular Languages

• Statement: If $L$ is regular, then $$\displaystyle \exists p > 0 $$ (pumping length) such that $\forall s \in L$ with $|s| \ge p$, $\exists x,y,z$ with $$\displaystyle s=xyz $$, $|xy| \le p$, $$\displaystyle |y| > 0 $$, and $\forall i \ge 0$, $$\displaystyle xy^iz \in L $$.

• Proving non-regularity:

  1. Assume $L$ regular, let $p$ be pumping length.

  2. Choose $s \in L$ with $|s| \ge p$ (usually $$\displaystyle s = a^p b^p $$ for $$\displaystyle \{a^n b^n\} $$).

  3. Show that for all decompositions $$\displaystyle s=xyz $$ with $|xy| \le p$, $$\displaystyle |y|>0 $$, $\exists i$ such that $$\displaystyle xy^iz \notin L $$.

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

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

  • Then $$\displaystyle y = a^k $$ for some $k \ge 1$.

  • Pump $$\displaystyle i=2 $$: $$\displaystyle |xy^2z| = q + k $$. Choose $i$ such that $q + (i-1)k$ is composite (e.g., $$\displaystyle i = q+1 $$ gives $q(1+k)$, composite). So $$\displaystyle xy^iz \notin L $$.

[!TIP] Choose $s$ that forces $y$ to be in a “critical” part (e.g., all a’s in $$\displaystyle \{a^n b^n\} $$). Pumping down ($$\displaystyle i=0 $$) often breaks balance.

III. CONTEXT-FREE GRAMMARS (CFG)

A. Definition and Components

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

  • $V$: set of non-terminals

  • $T$: set of terminals

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

  • $S \in V$: start symbol

• Derivation: Sequence of productions applied to start symbol to get a string.

  • Leftmost derivation: always replace leftmost non-terminal.

  • Rightmost derivation: always replace rightmost non-terminal.

B. Parse Trees (Derivation Trees)

• Construction: Root labeled $S$, each internal node labeled with non-terminal, children correspond to RHS of production, leaves labeled with terminals or $\varepsilon$.

• Yield: Concatenation of leaves from left to right (the derived string).

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

  
      S
  
     / \
  
    a   S
  
       / \
  
      a   b
  
  

  Yield: a a b b = aabb.

C. Ambiguity in Grammars

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

• Identifying ambiguity: Find a string with two distinct parse trees.

• Removal methods:

  • Left-factoring: Resolve common prefixes.

  • Grammar transformation: Rewrite to eliminate ambiguity (e.g., for if-then-else).

  • Unambiguous grammar: Construct equivalent unambiguous grammar.

[!TIP] Ambiguity is a property of the grammar, not the language. Some CFLs are inherently ambiguous (every CFG is ambiguous).

D. Normal Forms

• Chomsky Normal Form (CNF):

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

  • Conversion procedure:

    1. Remove $\varepsilon$-productions (except possibly $S \to \varepsilon$).

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

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

    4. Convert long RHS to binary: $A \to BCD$ becomes $A \to BE$, $E \to CD$.

• Greibach Normal Form (GNF):

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

  • Conversion:

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

    2. For each $$\displaystyle A_i $$, substitute productions of $$\displaystyle A_j $$ ($$\displaystyle j<i $$) that appear first on RHS.

    3. Eliminate left recursion for $$\displaystyle A_i $$.

    4. Ensure RHS starts with terminal followed by non-terminals with higher index.

E. Grammar Construction and Simplification

• Construction examples:

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

    \[ S \to AB,\quad A \to aAcc \mid \varepsilon,\quad B \to bBd \mid \varepsilon \]

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

    \[ S \to c \mid aSa \mid bSb \]

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

    \[ S \to AB,\quad A \to 011A \mid 1A \mid \varepsilon,\quad B \to 01B \mid \varepsilon \]

• Simplification:

  • Remove $\varepsilon$-productions:

    1. Find nullable variables (can derive $\varepsilon$).

    2. For each production $A \to \alpha$, add productions with nullable variables removed (except if $\alpha$ becomes empty and $A$ is not start).

    3. Remove $A \to \varepsilon$ if $\varepsilon \notin L$.

  • Remove unit productions:

    1. Compute unit pairs $(A,B)$ where $$\displaystyle A \Rightarrow^* B $$ via unit productions.

    2. For each unit pair $(A,B)$, add $A \to \gamma$ for every $B \to \gamma$ where $\gamma$ is not a single non-terminal.

    3. Remove all unit productions.

  • Remove useless symbols:

    1. Find generating symbols (derive terminal strings).

    2. Find reachable symbols from $S$ using generating symbols.

    3. Keep only generating and reachable symbols.

IV. PUSHDOWN AUTOMATA (PDA)

A. Definition and Model

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

  • $Q$: states

  • $\Sigma$: input alphabet

  • $\Gamma$: stack alphabet

  • $$\displaystyle \delta: Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^*) $$: transition function

  • $$\displaystyle q_0 $$: start state

  • $$\displaystyle z_0 \in \Gamma $$: initial stack symbol

  • $F \subseteq Q$: final states (for acceptance by final state)

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

• Transition: $(q, a, X) \to (p, \beta)$ means if input head reads $a$ (or $\varepsilon$), stack top $X$ is replaced by $\beta$ (pushed in reverse order), and state becomes $p$.

B. Types of PDA

• Non-deterministic PDA (NPDA): $\delta$ can map to multiple pairs.

• Deterministic PDA (DPDA):

  • For each $(q,a,X)$, at most one transition.

  • If $\delta(q,\varepsilon,X)$ defined, then $\delta(q,b,X)$ undefined for all $b \in \Sigma$.

• Acceptance modes:

  • By final state: Accept if some computation ends in $q \in F$ (stack arbitrary).

  • By empty stack: Accept if some computation ends with empty stack (state arbitrary).

C. PDA Design

• $$\displaystyle L = \{a^n b^n \mid n \ge 1\} $$ (by empty stack):

  • States: $$\displaystyle q_0 $$ (push a’s), $$\displaystyle q_1 $$ (pop on b’s).

  • Transitions:

    • $$\displaystyle \delta(q_0, a, z_0) = \{(q_0, a z_0)\} $$

    • $$\displaystyle \delta(q_0, a, a) = \{(q_0, a a)\} $$

    • $$\displaystyle \delta(q_0, \varepsilon, z_0) = \{(q_1, z_0)\} $$? Actually, on first b, go to $$\displaystyle q_1 $$: $$\displaystyle \delta(q_0, b, a) = \{(q_1, \varepsilon)\} $$

    • $$\displaystyle \delta(q_1, b, a) = \{(q_1, \varepsilon)\} $$

    • $$\displaystyle \delta(q_1, \varepsilon, z_0) = \{(q_2, \varepsilon)\} $$ (accept by empty stack, $$\displaystyle q_2 $$ is implicit).

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

  • Push a’s, ignore b’s, pop c’s.

• Even-length palindromes $$\displaystyle \{ww^R\} $$ (by empty stack):

  • States: $$\displaystyle q_0 $$ (push first half), $$\displaystyle q_1 $$ (pop and compare).

  • Transitions:

    • $$\displaystyle q_0 $$: on $a$ or $b$, push and stay; on $\varepsilon$, go to $$\displaystyle q_1 $$.

    • $$\displaystyle q_1 $$: on $a$, if stack top $a$, pop; on $b$, if stack top $b$, pop; on $\varepsilon$, if stack top $$\displaystyle z_0 $$, pop (accept).

• Odd-length palindromes $$\displaystyle \{w a w^R\} $$ (similar but with middle symbol):

  • Add state $$\displaystyle q_2 $$ to read middle symbol: from $$\displaystyle q_0 $$ on $\varepsilon$ go to $$\displaystyle q_2 $$, in $$\displaystyle q_2 $$ read one symbol (middle) and go to $$\displaystyle q_1 $$.

• $$\displaystyle \{w w^R w\} $$: Not context-free (cannot be recognized by any PDA).

• $$\displaystyle \{x \mid n_a(x)=n_b(x)\} $$: Push a’s, pop on b’s; also handle b’s before a’s by non-determinism.

[!TIP] For PDA by empty stack, ensure stack empties exactly when input ends. Use initial stack symbol $$\displaystyle z_0 $$ as marker.

D. Equivalence with CFG

• CFG to PDA (standard construction):

  • PDA simulates leftmost derivation.

  • Initially push $S$ onto stack.

  • For each production $A \to \alpha$, add transition: $\delta(q, \varepsilon, A) \ni (q, \alpha)$ (push $\alpha$ in reverse order).

  • For each terminal $a$, $\delta(q, a, a) \ni (q, \varepsilon)$.

  • Accept by empty stack.

• PDA to CFG:

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

  • Productions from transitions:

    • $\delta(p,a,X) \ni (r, \gamma)$ gives $[p,q] \to a [r,s] [t,q]$ etc. (detailed construction).

V. TURING MACHINES (TM)

A. Definition and Components

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

  • $Q$: states

  • $\Sigma$: input alphabet ($B \notin \Sigma$)

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

  • $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L,R\}$: transition function

  • $$\displaystyle q_0 $$: start state

  • $B$: blank symbol

  • $F \subseteq Q$: accept states

• Instantaneous description: $(q, u, \alpha, v)$ where tape = $u \alpha v$, head at $\alpha$, state $q$.

B. Techniques for TM Construction

• Marking symbols: Use extra tape symbols (e.g., $X$, $Y$) to mark visited cells.

• Multiple tracks: Use tape with multiple tracks to store multiple pieces of information (e.g., original input and counter).

• Storing counters: Use a portion of tape to store a counter (e.g., unary representation).

• Semi-infinite tape: Usually tape infinite to the right; left end may be bounded.

C. TM Design for Specific Languages

• Even number of 1’s:

  • States: $$\displaystyle q_{\text{even}} $$ (start), $$\displaystyle q_{\text{odd}} $$.

  • On 1, toggle state; on 0, stay; on blank, accept if in $$\displaystyle q_{\text{even}} $$.

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

  • Mark leftmost a as $X$, move right to first b, mark as $Y$, return left to next a.

  • Repeat until no a left; then check no b left.

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

  • Extend above: mark a as $X$, then b as $Y$, then c as $Z$; ensure order.

• $$\displaystyle w c w^R $$:

  • Find c, mark it.

  • For each symbol after c, move left to compare with corresponding symbol before c.

• Binary multiples of 3:

  • States represent remainder mod 3: $$\displaystyle q_0 $$, $$\displaystyle q_1 $$, $$\displaystyle q_2 $$.

  • Start in $$\displaystyle q_0 $$. For each bit $b$, new remainder $$\displaystyle r' = (2r + b) \bmod 3 $$.

  • Accept if final state $$\displaystyle q_0 $$.

• $$\displaystyle 0^n 1^{2n} $$:

  • For each 0, mark as $X$, then find and mark two 1’s as $Y$’s.

D. Variations of TM

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

• Non-deterministic TM: Multiple transitions; accepts if some computation accepts.

• Universal Turing Machine (UTM): TM that simulates any other TM given its description and input. Significance: Formalizes the notion of a programmable computer.

VI. DECIDABILITY AND UNDECIDABILITY

A. Language Classes

• Recursive (decidable): There exists a TM that halts on all inputs and accepts exactly $L$.

• Recursively enumerable (RE): There exists a TM that accepts $L$ (halts and accepts for $w \in L$, may loop for $w \notin L$).

• Relationships:

  \[ \text{Recursive} \subsetneq \text{RE} \]

  • Undecidable languages are RE but not recursive.

  • Some languages are not RE (e.g., complement of HALT).

B. Undecidable Problems

• Halting Problem:

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

  • Undecidable: No TM decides HALT.

  • Proof sketch: Reduce from acceptance problem $$\displaystyle A_{\text{TM}} = \{ \langle M, w \rangle \mid M \text{ accepts } w \} $$ (known undecidable). Construct TM that on input $\langle M, w \rangle$ simulates $M$ on $w$; if it halts, accept. This TM halts on all inputs iff HALT decidable, but $$\displaystyle A_{\text{TM}} $$ would then be decidable, contradiction.

• Post Correspondence Problem (PCP):

  • Given pairs $$\displaystyle (x_i, y_i) $$, $$\displaystyle i=1,\dots,k $$, find sequence $$\displaystyle i_1,\dots,i_m $$ such that $$\displaystyle x_{i_1}\dots x_{i_m} = y_{i_1}\dots y_{i_m} $$.

  • Undecidable: Reduction from TM acceptance.

  • Example: Pairs $(0,01), (100,001), (110,10)$. Check possible sequences: no solution.

• Other undecidable: Emptiness for TM, equivalence for TM.

C. Decidability Results

• Emptiness for TM: Given $M$, is $$\displaystyle L(M)=\emptyset $$? Undecidable.

• Equivalence for TM: Given $$\displaystyle M_1, M_2 $$, is $$\displaystyle L(M_1)=L(M_2) $$? Undecidable.

• Membership for CFL: Given CFG $G$ and string $w$, is $w \in L(G)$? Decidable via CYK algorithm ( $$\displaystyle O(n^3) $$ ).

VII. ADVANCED TOPICS AND PROOF TECHNIQUES

A. Mathematical Induction

• Weak induction: If $P(1)$ true and $P(k) \Rightarrow P(k+1)$ for all $k$, then $P(n)$ true $\forall n \in \mathbb{N}$.

• Strong induction: If $P(1)$ true and $P(1) \land \dots \land P(k) \Rightarrow P(k+1)$, then true for all $n$.

• Applications: Proving properties of languages (e.g., all strings in a regular language satisfy some property), correctness of constructions.

B. Chomsky Hierarchy

• Inclusions: Type-3 $\subsetneq$ Type-2 $\subsetneq$ Type-1 $\subsetneq$ Type-0.

• Separations: Known proper inclusions (e.g., $$\displaystyle \{a^n b^n c^n\} $$ is Type-1 but not Type-2).

C. Complexity Classes (Brief)

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

• NP: Problems verifiable in polynomial time by deterministic TM (or solvable by non-deterministic TM in polynomial time).

• NP-complete: Problems in NP that are NP-hard (every problem in NP reduces to them). Examples: SAT, 3-SAT, Clique, Vertex Cover.

• Significance: P vs NP problem (whether P = NP) is major open question.

D. Other Models

• Petri Nets:

  • Structure: bipartite graph with places (circles), transitions (rectangles), tokens (dots).

  • Applications: modeling concurrent systems, deadlock detection.

• Two-way DFA (2-DFA):

  • DFA that can move left and right on input tape.

  • Equivalent to standard DFA (can be simulated by DFA with more states).

• Composite Machines:

  • Interconnection of automata (e.g., product construction for intersection of regular languages).

E. Additional Topics from Past Papers

• Finite automata as language acceptors: state-based acceptance.

• Regular expression from automata: state elimination method.

• Leftmost/rightmost derivations for ambiguity checking.

• PDA by empty stack vs final state: empty stack acceptance is more general for CFLs? Actually, languages accepted by empty stack are those with $\varepsilon \in L$? Not exactly; but for CFGs, PDA by empty stack accepts all CFLs? Standard construction gives PDA by empty stack for any CFG. But some CFLs require final state acceptance? Actually, the two modes are equivalent for CFLs? Not exactly: PDA by empty stack accepts all CFLs that do not have $\varepsilon$? But with construction, we can accept by empty stack for any CFG by adding new start symbol. So both are equivalent for CFLs.

• Residue mod machines: for binary input, compute remainder modulo $m$ (see Mealy/Moore design).

• Simplification of CFG: removing $\varepsilon$-productions, unit productions, useless symbols (see Section III.E).

VIII. PROOF AND PROBLEM-SOLVING STRATEGIES

A. Proving Equivalence

• Between automata models:

  • NFA vs DFA: Use subset construction (construct DFA from NFA).

  • CFG vs PDA: Use standard constructions (CFG to PDA by simulating leftmost derivation; PDA to CFG by variables for state pairs).

• Closure properties: To show two languages are equivalent, show each is subset of the other using closure properties and known equivalences.

B. Proving Non-membership

• Pumping lemma for regular languages: As in Section II.D.

• Pumping lemma for CFLs (if asked): For CFL $L$, $\exists p$ such that $\forall s \in L$ with $|s| \ge p$, $$\displaystyle s=uvwxy $$ with $|vwx| \le p$, $$\displaystyle |vx|>0 $$, and $\forall i \ge 0$, $$\displaystyle uv^iwx^iy \in L $$.

• Closure properties: Show that if $L$ were regular/CFL, then some closure operation would yield a known non-regular/non-CFL language.

• Reduction: Reduce from known undecidable or non-regular language.

C. Construction Problems

• Designing automata for given languages:

  • Identify key features (counts, comparisons, palindromes).

  • Choose appropriate model (DFA for regular, PDA for CFL, TM for general).

  • Use standard techniques (stack for counting, marking for TM).

• Converting between representations:

  • DFA $$\displaystyle \leftrightarrow $$ RE: State elimination or Arden’s theorem.

  • CFG $$\displaystyle \leftrightarrow $$ PDA: Standard constructions.

  • Mealy $$\displaystyle \leftrightarrow $$ Moore: State splitting or output assignment.

  • NFA $$\displaystyle \leftrightarrow $$ DFA: Subset construction.

  • $\varepsilon$-NFA $\to$ NFA: $\varepsilon$-closure computation.