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

0. Preliminaries and Proof Techniques

Mathematical Induction

A proof technique for statements about natural numbers.

• Principle: If (i) Base case: $P(1)$ true, (ii) Inductive step: $P(k) \Rightarrow P(k+1)$ for all $k \ge 1$, then $P(n)$ true for all $n \ge 1$.

• Strong Induction: Assume $P(1), P(2), ..., P(k)$ true to prove $P(k+1)$. Useful for properties where $P(k)$ depends on multiple previous cases (e.g., Fibonacci).

• Applications: Proving correctness of algorithms, properties of automata (e.g., number of states after subset construction).

[!TIP]

Common Pitfall: Forgetting to prove the base case or misapplying the inductive hypothesis. In strong induction, explicitly state the assumption range.

I. Finite Automata (FA)

Deterministic Finite Automata (DFA)

Formal 5-tuple: $$\displaystyle M = (Q, \Sigma, \delta, q_0, F) $$

• $Q$: finite set of states

• $\Sigma$: input alphabet

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

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

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

Language Acceptance:

A string $w$ is accepted if the computation ends in a state from $F$. Formally, $$\displaystyle \hat{\delta}(q_0, w) \in F $$, where $\hat{\delta}$ is extended to strings.

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

States: $$\displaystyle q_0 $$ (start), $$\displaystyle q_1 $$, $$\displaystyle q_2 $$ (accept).
$$\displaystyle \delta(q_0,a)=q_0 $$, $$\displaystyle \delta(q_0,b)=q_0 $$, $$\displaystyle \delta(q_0,a)=q_1 $$? Wait, need correct design:

Better: $$\displaystyle q_0 \xrightarrow{a} q_0 $$, $$\displaystyle q_0 \xrightarrow{b} q_0 $$, $$\displaystyle q_0 \xrightarrow{a} q_1 $$, $$\displaystyle q_1 \xrightarrow{b} q_2 $$ (accept), $$\displaystyle q_2 \xrightarrow{a} q_1 $$, $$\displaystyle q_2 \xrightarrow{b} q_0 $$.

[!TIP]

Design Tip: For patterns like "ends with ab", track the last two symbols. Use a dead state for invalid transitions.

Non-deterministic Finite Automata (NFA)

5-tuple: $$\displaystyle M = (Q, \Sigma, \delta, q_0, F) $$

• $$\displaystyle \delta: Q \times (\Sigma \cup \{\epsilon\}) \to \mathcal{P}(Q) $$: maps to set of states (non-deterministic).

• ε-transitions: allow state changes without consuming input.

Language Acceptance:
$w$ accepted if exists a path from $$\displaystyle q_0 $$ to some $f \in F$ consuming $w$.

Example: NFA for strings containing "ab":

States $$\displaystyle q_0,q_1,q_2 $$ (accept).
$$\displaystyle \delta(q_0,a)=\{q_0,q_1\} $$, $$\displaystyle \delta(q_1,b)=\{q_2\} $$, others self-loop on $a,b$.

ε-NFA and ε-Closure

ε-closure of state $q$: set of states reachable from $q$ via ε-transitions (including $q$).

Denoted $ECLOSE(q)$.
Computation: On input $w$, from current set $S$, first take ε-closure of $S$, then for each symbol $a$ in $w$, move to $\bigcup \delta(s,a)$ for $s$ in closure, then take ε-closure again.

Conversion Between Automata

Subset Construction (NFA → DFA):

• DFA states: subsets of NFA states.

• Start state: $$\displaystyle ECLOSE(q_0) $$.

• Transition: $$\displaystyle \delta_{DFA}(S, a) = ECLOSE(\bigcup_{s \in S} \delta_{NFA}(s,a)) $$.

• Accepting states: any subset containing an NFA accept state.

ε-NFA → NFA: First compute ε-closures, then treat as NFA without ε-transitions.

DFA → NFA: Trivial (each DFA transition is a singleton set).

[!TIP]

Common Pitfall: Forgetting ε-closure after each symbol in subset construction. Always apply closure after moving on input.

Minimization of DFA

Goal: Unique minimal DFA for a regular language.

Table-Filling Algorithm:

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

2. Iteratively mark $(p,q)$ if $\exists a \in \Sigma$ such that $(\delta(p,a), \delta(q,a))$ is marked.

3. Unmarked pairs are equivalent; merge them.

Partitioning Method (Hopcroft’s):

• Start with partition: $F$ and $Q \setminus F$.

• Refine: split blocks where transitions on some $a$ go to different blocks.

• Repeat until stable. Merge states in same block.

Design of Finite Automata

Patterns:

• Exact counts: Use states representing count mod $k$.

• Substrings: Track progress toward substring (e.g., "ab" needs state after 'a').

• Prefixes/suffixes: Use states for partial matches.

• Overlapping patterns: May need extra states (e.g., "aaa" overlaps).

Example: DFA for exactly two $a$' and any $b$'s:

States: $$\displaystyle q_0 $$ (0 a's), $$\displaystyle q_1 $$ (1 a), $$\displaystyle q_2 $$ (2 a's, accept), $$\displaystyle q_3 $$ (more than 2 a's, dead).

Transitions: from $$\displaystyle q_0 $$ on $$\displaystyle a \to q_1 $$, $$\displaystyle b \to q_0 $$; $$\displaystyle q_1 $$ on $$\displaystyle a \to q_2 $$, $$\displaystyle b \to q_1 $$; $$\displaystyle q_2 $$ on $$\displaystyle a \to q_3 $$, $$\displaystyle b \to q_2 $$; $$\displaystyle q_3 $$ loops on all.

Finite Automata with Outputs

Mealy Machine: Output depends on current state and input.
6-tuple: $$\displaystyle (Q, \Sigma, \Delta, \delta, \lambda, q_0) $$ where $\Delta$ output alphabet, $\lambda: Q \times \Sigma \to \Delta$.

Moore Machine: Output depends only on current state.

Output function: $\lambda: Q \to \Delta$.

Conversion:

• Mealy → Moore: Split states with different outputs on same input into separate states. May increase states.

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

Comparison:

[!TIP]

Exam Focus: Converting Mealy to Moore: create new states for each unique (state, output) pair. For Moore to Mealy, use the state's output for all outgoing edges.

Two-way Finite Automata (2-DFA)

Head can move left or right on tape.

Formally: transition $\delta: Q \times \Sigma \to Q \times \{L,R\}$.
Equivalence: Accepts exactly regular languages (can be simulated by DFA).
Difference: More expressive in description but same power; may use less states for some languages.

Composite Machines

Product Construction for intersection:

Given DFA $$\displaystyle M_1=(Q_1,\Sigma,\delta_1,q_{01},F_1) $$, $$\displaystyle M_2=(Q_2,\Sigma,\delta_2,q_{02},F_2) $$,
$$\displaystyle M = (Q_1 \times Q_2, \Sigma, \delta, (q_{01},q_{02}), F_1 \times F_2) $$ where $$\displaystyle \delta((p,q),a) = (\delta_1(p,a), \delta_2(q,a)) $$.

Used to combine automata for languages like $$\displaystyle L_1 \cap L_2 $$.

II. Regular Expressions and Regular Languages

Regular Expressions (RE)

Built from:

• $\emptyset$ (empty set)

• $\epsilon$ (empty string)

• $a$ for $a \in \Sigma$

• Operations: union ($+$ or $|$), concatenation, Kleene star ($$\displaystyle ^* $$).

Example: Over $\{a,b\}$, strings ending with "ab": $$\displaystyle (a+b)^*ab $$.

Converting FA to RE (State Elimination)

1. Add new start state with ε-transition to old start, new final state with ε-transitions from old finals.

2. Eliminate states one by one: for state $q$ to eliminate, for each pair $p,r$ with paths $$\displaystyle p \xrightarrow{R_1} q \xrightarrow{R_2} r $$, add direct path $$\displaystyle p \xrightarrow{R_1 R_2^*} r $$ (if self-loop $$\displaystyle R_3 $$, use $$\displaystyle R_2^* = (R_2 + R_3 R_2^*) $$? Actually standard: if $q$ has self-loop with label $R$, then for $p \to q \to r$, add $$\displaystyle R_1 (R)^* R_2 $$).

3. Remaining edge label is RE for language.

Arden’s Theorem

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

Generalizes to systems of linear equations.

Application: Solve state equations for FA to get RE.

Example: For states $$\displaystyle q_1,q_2 $$ with equations:
$$\displaystyle q_1 = a q_1 + b q_2 + \epsilon $$
$$\displaystyle q_2 = a q_1 + b q_2 $$

Solve $$\displaystyle q_2 = a q_1 (b)^* $$? Actually: $$\displaystyle q_2 = a q_1 + b q_2 \Rightarrow q_2 = (a q_1) b^* $$. Substitute into $$\displaystyle q_1 $$: $$\displaystyle q_1 = a q_1 + b (a q_1 b^*) + \epsilon = (a + b a b^*) q_1 + \epsilon \Rightarrow q_1 = (a + b a b^*)^* $$. Then $$\displaystyle L = q_1 $$.

[!TIP]

Key: Ensure no ε in $A$ for Arden’s. If present, handle separately (ε means state is reachable without input).

Closure Properties of Regular Languages

Regular languages closed under:

Pumping Lemma for Regular Languages

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

Proving Non-regularity:

Assume $L$ regular, get $p$, choose $w$ cleverly (usually $$\displaystyle a^p b^p $$ or $$\displaystyle a^n b^n c^n $$), show no split satisfies pumping.

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

Proof: Take $$\displaystyle w = a^q $$ where $q$ is prime $$\displaystyle > p $$. Any split $$\displaystyle w=xyz $$ with $$\displaystyle |y|=k>0 $$, pump $$\displaystyle i=2 $$: $$\displaystyle |xy^2z| = q+k $$. For $$\displaystyle k=1 $$, $q+1$ composite (if $$\displaystyle q>2 $$), not prime. Contradiction.

[!TIP]

Common Mistake: Choosing $w$ not long enough or not considering all splits. Always ensure $|xy| \le p$ so $y$ consists only of $a$'s if $$\displaystyle w=a^p b^p $$.

III. Context-Free Grammars (CFG) and Languages

Context-Free Grammars

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

• $V$: variables (non-terminals)

• $T$: terminals

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

• $S \in V$: start symbol

Derivations:

• Leftmost: replace leftmost variable each step.

• Rightmost: replace rightmost variable.

• Parse Tree: internal nodes are variables, leaves terminals, yield = string.

• $$\displaystyle L(G) = \{ w \in T^* \mid S \Rightarrow^* w \} $$.

Example: $S \to aSb \mid ab$. Derive "aabb":

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

Parse tree: $S$ with children $a$, $S$, $b$; inner $S$ has $a$, $b$.

Ambiguity in CFG

Ambiguous grammar: $\exists$ string with two or more distinct parse trees (or leftmost derivations).
Inherently ambiguous language: all grammars generating it are ambiguous.

Classic Example: If-then-else:
$$\displaystyle S \to if\; E\; then\; S \;| \;if\; E\; then\; S\; else\; S \;| \;other $$

String "if E then if E then S else S" has two parses.

Removing Ambiguity:

• Rewrite grammar to enforce precedence/associativity.

• Example: For $E \to E+E \mid E*E \mid id$, enforce $*$ over $+$:
  $E \to E+T \mid T$, $T \to T*F \mid F$, $F \to id$.

Normal Forms for CFG

Chomsky Normal Form (CNF):

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

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

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

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

4. Convert remaining: for $A \to \alpha$ with $$\displaystyle |\alpha|>2 $$, introduce new variables to break into binary productions. For terminals in long RHS, replace with new variables.

Example: $S \to AB \mid a$, $A \to a$, $B \to b$ already in CNF.

Greibach Normal Form (GNF):
$A \to a\alpha$, $a \in T$, $$\displaystyle \alpha \in V^* $$ (no ε).
Conversion:

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

2. Eliminate left recursion by substitution.

3. Ensure RHS starts with terminal.

Example: $S \to A B A \mid B S \mid 1$, $B \to S A \mid 0$.

Order: $S, B$.

First eliminate left recursion in $S$? Actually $S$ has $B S$, so substitute $B$ equations into $S$ carefully.

Properties of Context-Free Languages

• Closed under: Union, concatenation, Kleene star.

• Not closed under: Intersection, complement.

  Example: $$\displaystyle L_1 = \{a^n b^n c^m\} $$, $$\displaystyle L_2 = \{a^m b^n c^n\} $$ are CFL, but $$\displaystyle L_1 \cap L_2 = \{a^n b^n c^n\} $$ not CFL.

Pumping Lemma for CFL:
$$\displaystyle \exists p > 0 $$ such that $\forall w \in L$ with $|w| \ge p$, $\exists u,v,w,x,y$ with $$\displaystyle w=uvwxy $$, $$\displaystyle |vx|>0 $$, $|vwx| \le p$, and $\forall i \ge 0$, $$\displaystyle uv^i w x^i y \in L $$.

Prove $$\displaystyle a^n b^n c^n $$ not CFL:

Assume regular, take $$\displaystyle w = a^p b^p c^p $$. Any split $uvwxy$ with $|vwx| \le p$: cases show pumping breaks balance.

Chomsky Hierarchy

Relations:
$$\displaystyle \text{Regular} \subset \text{CFL} \subset \text{CSL} \subset \text{RE} $$.

Not all inclusions proper? Regular ⊂ CFL proper (e.g., $$\displaystyle a^n b^n $$), CFL ⊂ CSL proper (e.g., $$\displaystyle a^n b^n c^n $$), CSL ⊂ RE proper (e.g., halting problem).

IV. Pushdown Automata (PDA)

PDA Definition and Model

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 \to \mathcal{P}(Q \times \Gamma^*) $$: transition (may push string)

• $$\displaystyle q_0 $$: start state

• $$\displaystyle Z_0 $$: initial stack symbol

• $F \subseteq Q$: accept states

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

Transition: $(q, aw, Za) \to (p, w, \beta)$ if $(p,\beta) \in \delta(q,a,Z)$.

Modes of Acceptance:

1. Final state: accept if reach state in $F$ with any stack.

2. Empty stack: accept if stack empty (any state).
   Equivalence: For CFL, both equivalent (but not for all languages; empty stack requires PDA to empty stack completely).

Deterministic vs Non-deterministic PDA

DPDA: $\forall (q,a,Z)$, at most one transition; if $(q,\epsilon,Z)$ defined, then no $(q,b,Z)$ for any $b \in \Sigma$.
Languages accepted: DCFL $\subset$ CFL (strict).

Example: Even-length palindromes are CFL but not DCFL? Actually $$\displaystyle \{ww^R\} $$ is DCFL? No, deterministic by pushing first half then popping. But $\{ww\}$ is not CFL.

Better example: $$\displaystyle \{a^i b^j c^k \mid i=j \text{ or } j=k\} $$ is CFL but not DCFL.

Design of PDA

Key Idea: Use stack to store unbounded memory (counters, markers).
Examples:

1. $$\displaystyle L = \{a^n b^n \mid n \ge 1\} $$:

   • Push $a$'s, pop on $b$'s.

   • Transitions: $$\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_2, Z_0) $$ accept.

2. Palindromes $$\displaystyle ww^R $$:

   • Non-deterministically guess midpoint: push first half, then pop matching second half.

   • Or: push symbols until guess, then pop matching.

Conversion Between CFG and PDA

CFG → PDA (standard construction):

• PDA simulates leftmost derivation.

• Initially push $S$.

• If top is variable $A$, replace by RHS of some $A \to \alpha$ (pop $A$, push $\alpha$ in reverse order).

• If top is terminal $a$, match with input (pop and consume).

• Accept by empty stack.

PDA → CFG:

• For each pair of states $p,q$, create variable $$\displaystyle A_{pq} $$ representing substrings that take PDA from $p$ to $q$ with stack empty at both ends.

• Add productions based on transitions.

Complex; see standard construction.

Closure Properties of CFLs via PDA

• Union: Combine PDAs with new start state ε-transitions to each PDA's start.

• Concatenation: ε from finals of first PDA to start of second.

• Kleene star: New start/final with ε-loops to PDA.

• Not closed under intersection/complement: Counterexample: $$\displaystyle L_1 = \{a^i b^j c^k \mid i=j\} $$, $$\displaystyle L_2 = \{a^i b^j c^k \mid j=k\} $$ both CFL, intersection $$\displaystyle \{a^n b^n c^n\} $$ not CFL.

V. Turing Machines (TM) and Decidability

Turing Machine Definition

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

• $Q$: finite 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\}$

• $$\displaystyle q_0 $$: start state

• $B$: blank symbol

• $F$: accept states

Computation: Tape infinite both directions, head moves L/R, writes symbol, changes state. Halts if no transition defined or in $F$.

Techniques for TM Construction

1. Scanning: Move right/left to find symbol.

2. Marking: Change symbol to mark visited (e.g., replace $a$ with $X$).

3. Shifting: Move tape content (multiple tracks help).

4. Simulating subroutines: Modular design with states.

Design of Turing Machines

Example 1: Even number of 1's over $\{0,1\}$.

• States: $$\displaystyle q_0 $$ (even), $$\displaystyle q_1 $$ (odd), $$\displaystyle q_{accept} $$.

• $$\displaystyle \delta(q_0,0)=(q_0,0,R) $$, $$\displaystyle \delta(q_0,1)=(q_1,1,R) $$, $$\displaystyle \delta(q_1,0)=(q_1,0,R) $$, $$\displaystyle \delta(q_1,1)=(q_0,1,R) $$.

• On blank, if in $$\displaystyle q_0 $$ go to accept, else reject.

Example 2: $$\displaystyle a^n b^n c^n $$:

• Phase 1: mark first $a$ as $X$, go right to first $b$, mark as $Y$, then to first $c$, mark as $Z$, return to start.

• Repeat until all marked. Check no extra symbols.

Variants of Turing Machines

• Multi-tape TM: Multiple tapes, independent heads.

  Equivalence: Can simulate single-tape TM with quadratic slowdown (use separators).

• Non-deterministic TM: Multiple transitions.

  Equivalence: Deterministic TM can simulate (breadth-first search on configuration tree, may not halt on non-halting branches).

• Universal Turing Machine (UTM):

  Takes as input: encoding of TM $M$ and string $w$.

  Simulates $M$ on $w$.

  Significance: Shows existence of "general-purpose" computer; foundation for computability theory.

Decidability

• Recursive (Decidable): $L$ such that $\exists$ TM halts on all inputs, accepts $w \in L$, rejects $w \notin L$.

• Recursively Enumerable (RE) (Semi-decidable): $\exists$ TM halts and accepts $w \in L$, may loop forever on $w \notin L$.

• Relationship: $\text{Recursive} \subset \text{RE}$ (proper: halting problem is RE but not recursive).

Undecidable Problems

Halting Problem:
$$\displaystyle H_{TM} = \{ \langle M, w \rangle \mid M \text{ halts on } w \} $$.
Undecidable: No TM decides $$\displaystyle H_{TM} $$.
Proof (reduction from $$\displaystyle A_{TM} $$): Assume decider $H$ for halting, construct decider for $$\displaystyle A_{TM} = \{ \langle M,w \rangle \mid M \text{ accepts } w \} $$:

On input $\langle M,w \rangle$, construct $M'$ that on any input simulates $M$ on $w$; then $M'$ halts iff $M$ accepts $w$. Use $H$ on $\langle M', \epsilon \rangle$ to decide $$\displaystyle A_{TM} $$. Contradiction since $$\displaystyle A_{TM} $$ undecidable.

Post Correspondence Problem (PCP):

Given dominos $$\displaystyle (x_i, y_i) $$, find sequence $$\displaystyle i_1,...,i_k $$ such that $$\displaystyle x_{i_1}...x_{i_k} = y_{i_1}...y_{i_k} $$.
Undecidable: Reduction from halting problem.

Rice’s Theorem:

Any non-trivial property of RE languages is undecidable.

Non-trivial: not true for all RE languages, not false for all.

Example: "Is $L(M)$ regular?" undecidable.

VI. Complexity Theory

Complexity Classes

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

  $$\displaystyle P = \bigcup_{k \ge 1} DTIME(n^k) $$.

• NP: Languages decidable by non-deterministic TM in polynomial time, or equivalently, problems with polynomial-time verifiable certificates.

  $$\displaystyle NP = \bigcup_{k \ge 1} NTIME(n^k) $$.

• NP-complete: $L \in NP$ and $\forall L' \in NP$, $$\displaystyle L' \le_p L $$ (polynomial-time reducible).

• NP-hard: $L$ such that $\forall L' \in NP$, $$\displaystyle L' \le_p L $$ (may not be in NP).

Examples of NP-complete:

• SAT: Satisfiability of Boolean formula.

• 3-SAT: SAT with clauses of 3 literals.

• Clique: Given graph $G$, integer $k$, does $G$ have $k$-clique?

• Vertex Cover: Given $G,k$, does $G$ have vertex cover of size $\le k$?

• Hamiltonian Cycle: Given $G$, does it have cycle visiting each vertex once?

Reductions

To prove $L$ NP-hard: reduce known NP-complete problem to $L$ in polynomial time.

Example: Reduce 3-SAT to Clique:

Given 3-SAT formula with $m$ clauses, construct graph with $3m$ vertices (one per literal), edges between non-conflicting literals from different clauses. Then formula satisfiable iff graph has $m$-clique.

VII. Advanced Topics (from Past Papers)

Petri Nets

Components:

• Places (circles): hold tokens.

• Transitions (rectangles): fire when input places have enough tokens.

• Arcs: directed from places to transitions or transitions to places.

• Marking: distribution of tokens over places (initial marking given).

Firing Rule: Transition fires if each input place has at least as many tokens as arc weight. Then consume tokens from input places, produce tokens in output places.

Applications: Modeling concurrent, parallel, distributed systems (e.g., communication protocols, manufacturing).

Example: Simple net with two places $$\displaystyle P_1,P_2 $$, transition $T$: arcs $$\displaystyle P_1 \to T $$ (weight 1), $$\displaystyle T \to P_2 $$ (weight 1). Initial marking: $$\displaystyle P_1 $$ has 1 token. Fire $T$: token moves to $$\displaystyle P_2 $$.

Linear Bounded Automata (LBA)

TM where tape limited to region containing input (size linear in input length).
Languages: Context-sensitive (Type 1).
Equivalence: LBA $$\displaystyle \leftrightarrow $$ context-sensitive grammars.
Difference from TM: Tape not infinite; may halt on space overflow.

Other Topics

• 2-stack PDA: Equivalent to TM (one stack simulates tape, other stores position).

• Two-way DFA: Already covered in Finite Automata section.

Summary of Key Formulas and Theorems

[!TIP]

Exam Strategy:

1. For conversion questions (NFA→DFA, CFG→CNF, Mealy→Moore), follow step-by-step algorithms strictly.

2. For design questions (DFA, PDA, TM), first identify pattern, then choose appropriate technique (stack for counting, marking for TM).

3. For proofs (non-regular, non-CFL, undecidability), use pumping lemma or reduction clearly.

4. Remember equivalences: NFA=DFA, PDA acceptance modes, multi-tape TM=single-tape.

5. Common mistakes: Forgetting ε-closure in subset construction, incorrect CNF conversion (missing step), misapplying pumping lemma split condition.