UNIT 4: THEORY OF COMPUTATION - EXAM-FOCUSED SHORT NOTES

Based on exhaustive analysis of RGPV past papers (Dec 2025, Dec 2024, May 2023, Nov 2023, Nov 2022, Jun 2025, May 2024).

I. FINITE AUTOMATA & FINITE STATE MACHINES

A. Fundamental Concepts

• Finite Automaton (FA): A simple computational model that accepts/rejects strings based on state transitions. It has finite memory (states only).

• Deterministic Finite Automaton (DFA):

  • Formal Definition: $$\displaystyle M = (Q, \Sigma, \delta, q_0, F) $$

    • $Q$: Finite set of states.

    • $\Sigma$: Input alphabet.

    • $\delta$: Transition function $$\displaystyle Q \times \Sigma \rightarrow Q $$.

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

    • $F$: Set of final/accepting states.

  • Key Feature: For each state and input symbol, exactly one next state.

• Non-deterministic Finite Automaton (NFA/ε-NFA):

  • Formal Definition: $$\displaystyle M = (Q, \Sigma, \delta, q_0, F) $$

    • $\delta$: Transition function $$\displaystyle Q \times (\Sigma \cup \{\epsilon\}) \rightarrow \mathcal{P}(Q) $$ (power set of Q).

  • Key Features: Can have multiple next states for a symbol; can move on ε (empty string) without consuming input.

  • ε-closure(q): Set of states reachable from state q via ε-transitions alone (including q itself).

• Language Acceptance: A string w is accepted if, starting from q_0 and processing w, the automaton ends in a final state.

[!TIP] EXAM TIP: NFA/ε-NFA are equivalent to DFA in expressive power (both recognize Regular Languages). The conversion NFA→DFA is a very high frequency exam question.

B. Conversions & Constructions (High Frequency)

1. Subset Construction (NFA/ε-NFA → DFA)

• Idea: Each DFA state represents a set of NFA states.

• Steps:

  1. Start state of DFA = ε-closure(q₀).

  2. For each DFA state S (a set of NFA states) and each symbol a ∈ Σ:

     • Compute T = ∪ δ(s, a) for all s ∈ S.

     • New DFA state = ε-closure(T).

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

• Result: DFA may have up to $$\displaystyle 2^{|Q|} $$ states.

2. Thompson's Construction (RE → ε-NFA)

• Builds an ε-NFA for a given Regular Expression (RE) recursively.

• Base Cases:

  • For ∅: No states.

  • For ε: Single transition q₀ → ε → q₁.

  • For symbol a: Single transition q₀ → a → q₁.

• Inductive Steps:

  • Union (R₁ + R₂): New start/final states with ε-transitions to/from R₁ and R₂ NFAs.

  • Concatenation (R₁R₂): Final state of R₁ connected via ε to start state of R₂.

  • Kleene Star (R)*: New start/final states. ε from new start to R's start and to new final. ε from R's final back to R's start and to new final.

• Result: ε-NFA with exactly one start and one final state.

3. State Elimination Method (DFA/NFA → RE)

• Procedure:

  1. Ensure a single start (add new start with ε-transition if needed) and single final state (add new final with ε-transitions from all finals).

  2. Repeatedly eliminate a non-start, non-final state q:

     • For every pair of states p, r that have paths through q, add a new direct path: label(p→q) · (label(q→q))* · label(q→r).

     • Remove q and all its incident transitions.

  3. The remaining direct transition from start to final gives the RE.

4. Composite Machine Construction

• Union (L₁ ∪ L₂): Build NFA with new start state having ε-transitions to starts of L₁ and L₂ automata. Final states remain as is.

• Intersection (L₁ ∩ L₂): Use De Morgan's Law: $$\displaystyle L₁ ∩ L₂ = \overline{\overline{L₁} ∪ \overline{L₂}} $$. Complement requires DFA (swap final/non-final).

• Concatenation (L₁L₂): Connect final states of L₁ to start state of L₂ via ε-transitions. Start state = start of L₁. Final states = final states of L₂.

C. Finite Automata with Outputs

[!TIP] EXAM TIP: Converting Mealy to Moore often increases states; converting Moore to Mealy keeps state count same.

D. Analysis & Minimization

• Minimization of DFA (Table-Filling / Partitioning Method):

  1. Initial Partition: Split states into FINAL and NON-FINAL groups.

  2. Refinement: For each group G and symbol a, check if states in G transition to states in different groups. If yes, split G.

  3. Repeat until no more splits.

  4. Each group becomes a single minimized state.

• Dead State: A non-final state with self-loops on all symbols (sink state). Often omitted in diagrams but crucial for minimization.

• Generating Strings of Length ≤ k: Perform BFS/DFS from start state, tracking path labels, up to depth k. Collect strings ending in final states.

E. Specialized/Advanced FA (Lower Frequency)

• Two-way Finite Automaton (2-DFA): Head can move left or right. Power equivalent to standard DFA (can be simulated by a DFA), but may require more states.

• Residue/Modulo DFA (e.g., mod 3):

  • States represent remainders (0, 1, 2 for mod 3).

  • Transition: $$\displaystyle \delta(r, a) = (2r + a) \mod 3 $$ for binary input.

  • Final state = remainder 0.

II. REGULAR LANGUAGES & EXPRESSIONS

A. Regular Expressions (RE)

• Definition: Algebraic description of a regular language using operators:

  • Union (+): r₁ + r₂

  • Concatenation: r₁r₂

  • Kleene Star (*): r* (zero or more repetitions)

  • Precedence: * > concatenation > +.

• Common Constructions:

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

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

  • Length divisible by 3 or 5: ( (000+111)* + (00000+11111)* ) (over {0,1})

B. Arden's Theorem (Very High Frequency)

• Statement: If R and S are REs and ε ∉ R, then the equation X = R X + S has a unique solution: X = R* S.

• Application to FA → RE:

  1. For each state qᵢ, write an equation: qᵢ = Σ (δ(qᵢ, a) qⱼ) + ε if qᵢ is start.

  2. Solve the system of equations using Arden's Theorem (substitute, eliminate).

  3. The RE for the language is the solution for the start state.

• Steps:

  1. Eliminate non-reachable states first.

  2. Arrange equations so that LHS is the state to eliminate.

  3. Substitute RHS expressions, applying X = R X + S → X = R* S.

  4. The final expression for start state is the answer.

[!TIP] EXAM TIP: Arden's is guaranteed to work for right-linear grammars/DFAs. Always check for ε in R; if present, use R+ or restructure.

C. Closure Properties of Regular Languages (Very High Frequency)

[!TIP] EXAM TIP: To prove a language is not regular, use Pumping Lemma. Closure properties are used to reduce a known non-regular language to the target via operations that preserve regularity.

D. Pumping Lemma for Regular Languages

• Statement: If L is regular, then ∃ a pumping length p ≥ 1 such that any string s ∈ L with |s| ≥ p can be split as s = xyz satisfying:

  1. |y| > 0

  2. |xy| ≤ p

  3. ∀ i ≥ 0: xyⁱz ∈ L

• Proof Strategy (to show L is not regular):

  1. Assume L is regular → ∃ pumping length p.

  2. Choose a specific string s ∈ L with |s| ≥ p (often s = a^p b^p or similar).

  3. Consider all possible splits s = xyz with |xy| ≤ p, |y|>0.

  4. Show for at least one split, xyⁱz ∉ L for some i (usually i=0 or i=2).

  5. Contradiction → L not regular.

[!TIP] EXAM TIP: For L = {aⁿ bⁿ}, choose s = a^p b^p. Since |xy|≤p, y consists only of a's. Pumping i=0 gives fewer a's than b's → not in L.

III. CONTEXT-FREE GRAMMARS (CFG) & LANGUAGES (CFL)

A. CFG Fundamentals

• Formal Definition: $$\displaystyle G = (V, T, P, S) $$

  • V: Finite set of non-terminals (variables).

  • T: Finite set of terminals (alphabet).

  • P: Finite set of productions of form A → α, A ∈ V, α ∈ (V ∪ T)*.

  • S: Start symbol (S ∈ V).

• Derivation: Applying productions to replace a non-terminal. Leftmost (replace leftmost NT first), Rightmost (replace rightmost NT first).

• Parse Tree: Tree representation of derivation. Root = S. Interior nodes = NTs, leaves = terminals. Yield = string read left-to-right from leaves.

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

B. Ambiguity in Grammar (High Frequency)

• Definition: A CFG G is ambiguous if ∃ a string w ∈ L(G) that has more than one parse tree (or equivalently, more than one leftmost/rightmost derivation).

• Identification: For a given string, explicitly construct two different leftmost derivations.

• Methods to Remove Ambiguity:

  1. Left-factoring: Factor common prefixes.

     • A → aB | aC becomes A → aA', A' → B | C.

  2. Introduce new non-terminals to enforce precedence/association.

     • For arithmetic: E → E + T | T, T → T * F | F (resolves a+b*c).

  3. Rewrite grammar to be unambiguous (may change language slightly if not careful).

C. Normal Forms for CFG (Very High Frequency)

Chomsky Normal Form (CNF)

• Definition: Every production is of form:

  1. A → BC (two non-terminals)

  2. A → a (one terminal)

  3. S → ε (only if empty string is in language; S cannot appear on RHS).

• Conversion Steps:

  1. Eliminate ε-productions (A → ε):

     • Find nullable NTs (can derive ε).

     • For each production A → α, add new productions with all combinations of nullable NTs in α removed (except keep ε if α all nullable).

     • Remove ε-productions (except possibly S → ε).

  2. Eliminate unit productions (A → B):

     • For each A → B, add A → γ for all B → γ (where γ is not a single NT).

     • Remove all unit productions.

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

  4. Convert long productions (A → α where |α| ≥ 3):

     • Replace A → B₁B₂...Bₖ (k≥3) with A → B₁C₁, C₁ → B₂C₂, ..., Cₖ₋₂ → Bₖ₋₁Bₖ, introducing new NTs Cᵢ.

  5. Convert mixed productions (A → aB or A → Ba):

     • Replace terminal a with a new NT Aₐ and add Aₐ → a.

     • Apply step 4.

Greibach Normal Form (GNF)

• Definition: Every production is of form A → aα, where a ∈ T, α ∈ V* (string of zero or more NTs).

• Conversion Steps (Outline):

  1. Ensure start symbol doesn't appear on RHS (add new start S₀ → S if needed).

  2. Order NTs: A₁, A₂, ..., Aₙ.

  3. For i = 1 to n:

     • Eliminate left-recursion for Aᵢ.

     • Replace Aⱼ (j < i) on RHS of Aᵢ's productions using existing Aⱼ → aα forms.

  4. Convert remaining productions to A → aα.

[!TIP] EXAM TIP: CNF is more common in exams. In CNF, parse tree height is log₂|w| for string w. GNF is used for PDA construction (leftmost derivation simulation).

D. Properties & Constructions

• Simplifying CFG:

  • Remove useless symbols: NT A is useless if:

    1. A does not derive any terminal string (non-generating).

    2. A is not reachable from start symbol.

• Constructing CFG from RE:

  • For ∅, ε, a: trivial.

  • For R₁ + R₂: S → S₁ | S₂.

  • For R₁R₂: S → S₁S₂.

  • For R*: S → SS₁ | ε.

• Constructing CFG for Complex Languages:

  • {aᵐ bⁿ c²ᵐ dⁿ}: S → aScD | T, T → bTd | ε.

  • {w c wᴿ}: S → c | aSa | bSb.

• Proving a Language is NOT Context-Free:

  • Pumping Lemma for CFL: If L is CFL, ∃ p such that any s ∈ L with |s|≥p can be split s=uvwxy with:

    1. |vwx| ≤ p

    2. |vx| > 0

    3. ∀ i ≥ 0: u vⁱ w xⁱ y ∈ L

  • Closure Properties: CFLs are not closed under intersection/complement. Use: if L were CFL, then L ∩ R (with regular R) would be CFL. Choose R so that L ∩ R is known non-CFL (e.g., {aⁿ bⁿ cⁿ}).

• Closure Properties of CFLs:

  • ✅ Union, Concatenation, Kleene Star.

  • ❌ Intersection, Complement, Difference.

  • ✅ Intersection with Regular (PDA with two stacks? No: L ∩ R is CFL if L is CFL and R is regular).

IV. PUSHDOWN AUTOMATA (PDA)

A. PDA Model

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

  • Q: Finite states.

  • Σ: Input alphabet.

  • Γ: Stack alphabet.

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

    • Input: (current state, current input symbol or ε, stack top)

    • Output: Set of (next state, string to replace stack top).

  • q₀: Start state.

  • Z₀: Initial stack symbol.

  • F: Set of final states (for final state acceptance).

• Instantaneous Description (ID): (q, w, γ) where:

  • q: current state.

  • w: unread input.

  • γ: current stack contents (top on left).

• Modes of Acceptance:

  1. Final State: Accept if, after reading entire input, PDA is in a state in F (stack can be non-empty).

  2. Empty Stack: Accept if, after reading entire input, stack is empty (state can be any).

B. Deterministic vs. Non-deterministic PDA

• DPDA: For any ID (q, a, A):

  • At most one transition.

  • If δ(q, a, A) is non-empty, then δ(q, ε, A) must be empty.

• NPDA: No such restriction.

• Power: NPDA > DPDA. All DPDA languages are CFL, but some CFLs (e.g., even-length palindromes {wwᴿ}) are not deterministic CFL (require NPDA).

• Example: L = {aⁿ bⁿ cⁿ | n≥1} is not CFL, but L = {aⁿ bⁿ} is DCFL (accepted by DPDA by final state).

C. PDA Design (Very High Frequency)

Design by Final State

• Idea: Use stack to match symbols, then move to final state.

• Example: L = {aⁿ bⁿ | n≥1}

  • Push a's onto stack.

  • For each b, pop one a.

  • Accept if input ends and stack has only Z₀ (or pop Z₀ on last b and go to final state).

• Example: L = {x | nₐ(x) = n_b(x)} (order doesn't matter)

  • Push a for a, pop a for b.

  • If stack empty when reading b, push b (or use two stack symbols).

  • Accept if stack empty at end.

Design by Empty Stack

• Idea: Ensure stack is exactly empty after processing.

• Example: L = {aⁿ bⁿ | n≥0}

  • Push a's.

  • For each b, pop one a.

  • At end, pop Z₀ via ε-move to empty stack.

• Example: L = {aⁿ b³ⁿ | n≥0}

  • For each a, push three markers (e.g., XXX).

  • For each b, pop one marker.

  • Accept when stack empty.

• Example: Even-length palindromes {wwᴿ}

  • Non-deterministically guess midpoint.

  • Push first half symbols.

  • For second half, pop and match.

  • Empty stack at end.

• Example: Odd-length palindromes {w a wᴿ}

  • Similar, but middle symbol a is skipped (ε-transition after reading a).

[!TIP] EXAM TIP: For {w c wᴿ}, push symbols before c, then after c, pop and match. Use c as midpoint marker.

D. Conversion between CFG and PDA

CFG → PDA (by empty stack) - Standard Construction

• Idea: Simulate leftmost derivation.

• Construction:

  1. PDA has one state q.

  2. Initial stack symbol = start symbol S of CFG.

  3. Transitions:

     • For each terminal a: δ(q, ε, A) contains (q, a) if A → a is a production.

     • For each production A → α: δ(q, ε, A) contains (q, α) (push α in reverse order).

  4. On input w, PDA will non-deterministically choose productions to derive w on stack, then match terminals with input. Accept by empty stack.

• To convert to final state acceptance: Add new start state q₀ and new final state q_f. From q₀, ε-move to q with S on stack. From q, when stack empty (only Z₀), ε-move to q_f.

PDA → CFG

• Idea: For every pair of states (p, q) and stack symbol A, create a variable [p A q] generating strings that take PDA from state p to q with A on top initially and popping it.

• Procedure (Outline):

  1. For each transition δ(r, a, B) = (s, γ) where γ = C₁C₂...Cₖ:

     • Add productions: [r B s] → a [s C₁ t₁] [t₁ C₂ t₂] ... [tₖ₋₁ Cₖ s] for all intermediate states tᵢ.

  2. For ε-transitions δ(r, ε, B) = (s, ε):

     • Add [r B s] → ε.

  3. Start variable = [q₀ Z₀ q_f] for some final state q_f (or use empty stack method).

V. TURING MACHINES (TM)

A. TM Model & Definition

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

  • Q: Finite states.

  • Σ: Input alphabet (B ∉ Σ).

  • Γ: Tape alphabet (Σ ⊆ Γ, B ∈ Γ).

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

  • q₀: Start state.

  • B: Blank symbol.

  • F: Set of final states.

• Instantaneous Description (ID): u q v where tape content is u v (head at first symbol of v).

• Transition: δ(q, a) = (p, b, D) means: in state q reading a, write b, move head D (L or R), go to state p.

B. Techniques for TM Construction (Very High Frequency)

1. Marking Symbols: Change symbol to a marked version (e.g., a → a') to remember processed symbols.

2. Shuttling: Move head back and forth between ends of input (e.g., to match a with b).

3. Multi-tape TM: Easier to design (e.g., copy input to second tape). Equivalent to single-tape TM (can simulate with one tape using delimiters).

4. Subroutines: Modular design (e.g., subroutine to increment binary number, to copy string).

5. Storage in Finite Control: If the amount of information to store is bounded (e.g., parity, small count), can store in state itself.

C. TM Design Problems (Very High Frequency)

1. L = {aⁿ bⁿ | n ≥ 1}

• Technique: Marking & shuttling.

  1. Scan right to find first unmarked a, mark it (a → X).

  2. Scan right to find first unmarked b, mark it (b → Y).

  3. Repeat until no unmarked a or b. Accept if all b's marked and no extra a's.

• Transition sketch:

  • q₀: Move right, if a → X, go to q₁ (search for b); if b → reject; if Y → check all Y then accept.

  • q₁: Move right, skip X/Y, if b → Y, go to q₂ (return to left).

  • q₂: Move left, skip X/Y, if X → go to q₀.

2. L = {aⁿ bⁿ cⁿ | n ≥ 1}

• Technique: Mark in pairs.

  1. Mark first a (a → X).

  2. Find first unmarked b, mark (b → Y).

  3. Find first unmarked c, mark (c → Z).

  4. Repeat. Accept if all a,b,c marked simultaneously.

3. L = {w c wᴿ | w ∈ {0,1}*}

• Technique: Match symbols symmetrically around c.

  1. Scan right to find c, mark it (c → C).

  2. Move left to first unmarked symbol (start of w), mark it (0→X, 1→Y).

  3. Move right to C, then right to first unmarked after C (start of wᴿ), check if matches mark (X→0, Y→1), mark as Z.

  4. Repeat inward. Accept if all symbols matched and C is only between.

4. Even number of 1's over {0,1}

• Technique: Store parity in state.

  • States: q_even (even 1's seen), q_odd (odd 1's seen).

  • On 0: stay in same state.

  • On 1: toggle between q_even and q_odd.

  • Accept in q_even at end of input.

5. Binary numbers divisible by 3

• Technique: Remainder in state.

  • States: q₀ (remainder 0), q₁ (remainder 1), q₂ (remainder 2).

  • Transition: δ(qᵣ, a) = q_{(2r + a) mod 3}.

  • Accept in q₀.

6. Multiplication of two unary numbers (aⁿ and aᵐ)

• Technique: Copy and add.

  1. Separate two numbers by # (e.g., aⁿ # aᵐ).

  2. For each a in second number, copy the first number to the end (using marking).

  3. At end, count total a's (or erase separators and leave product).

D. Advanced TM Concepts

• Universal Turing Machine (UTM): A TM U that takes as input encoding of any TM M and string w, and simulates M on w.

  • Significance: Shows existence of a general-purpose computer. Proves that the set of TMs is enumerable.

• TM as Enumerator: TM that prints strings of a language (may not halt). Enumerates RE languages.

• Semi-infinite tape: Tape infinite only to the right. Equivalent to infinite tape (can simulate with two stacks).

VI. DECIDABILITY, UNDECIDABILITY & COMPLEXITY

A. Language Classes

[!TIP] EXAM TIP: A_TM = {<M,w> | M accepts w} is RE but not recursive. HALT_TM is also RE but not recursive. E_TM = {<M> | L(M)=∅} is not RE.

B. Undecidable Problems (Very High Frequency)

1. The Halting Problem (HP)

• Statement: HALT_TM = {<M, w> | TM M halts on input w}.

• Undecidability Proof (by reduction from A_TM):

  1. Assume HALT_TM is decidable by TM H.

  2. Construct TM D that on input <M, w>:

     • Run H on <M, w>.

     • If H rejects (does not halt), accept.

     • If H accepts (halts), loop forever.

  3. Consider D on its own encoding <D>. Contradiction arises.

• Alternative Proof: Diagonalization (construct TM that halts iff given TM does not halt on its own encoding).

2. Acceptance Problem A_TM

• A_TM = {<M, w> | M accepts w}.

• Undecidable (diagonalization proof).

• RE: Simulate M on w; accept if M accepts.

3. Post Correspondence Problem (PCP)

• Instance: Finite set of pairs {(x₁, y₁), (x₂, y₂), ..., (xₖ, yₖ)} where xᵢ, yᵢ ∈ Σ*.

• Question: Is there a sequence of indices i₁, i₂, ..., iₙ such that x_{i₁} x_{i₂} ... x_{iₙ} = y_{i₁} y_{i₂} ... y_{iₙ}?

• Undecidable (reduction from A_TM).

• Solving Small Instances (Exam):

  • Try all sequences up to a reasonable length.

  • Look for top/bottom strings that can match.

  • Example: {(ba, bab), (100, 001), (110, 10)} → try (2,3,1): 100110ba vs 0011010bab → no match. Usually no solution.

4. Other Undecidable Problems

• E_TM (Emptiness): {<M> | L(M)=∅} — not RE.

• REGULAR_TM: {<M> | L(M) is regular} — undecidable.

• EQ_TM: {<M₁, M₂> | L(M₁)=L(M₂)} — undecidable.

C. Complexity Classes (High Frequency)

• Reductions: L₁ ≤ₚ L₂ means L₁ is polynomial-time reducible to L₂. If L₂ ∈ P then L₁ ∈ P.

• Cook-Levin Theorem: SAT is NP-Complete (first NPC problem).

• Common NPC Problems: SAT, 3-SAT, Clique, Vertex Cover, Hamiltonian Path, Subset Sum.

[!TIP] EXAM TIP: Halting Problem is NP-Hard (since all NP problems reduce to it? Actually, HP is not NP-Hard unless NP ⊆ RE? Wait: HP is undecidable, so it's not in NP. But is it NP-Hard? NP-Hard means all NP problems reduce to it. Since NP problems are decidable, and undecidable problems are "harder", yes, any decidable problem reduces to an undecidable one? Not necessarily in polynomial time. Actually, standard: Halting Problem is not NP-Hard because NP-Hard problems must be at least as hard as NP, but HP is undecidable, and reductions from decidable to undecidable may not exist in polynomial time. Correct: HP is not known to be NP-Hard; it's undecidable and not in NP. Better: NP-Complete problems are decidable. HP is undecidable, so it's not in NP, hence not NP-Complete. But can it be NP-Hard? For a problem to be NP-Hard, every problem in NP must reduce to it in polynomial time. Since NP problems are decidable, if an undecidable problem were NP-Hard, then all NP problems would be reducible to an undecidable problem, which would imply NP problems are undecidable — contradiction. So undecidable problems cannot be NP-Hard (unless NP contains undecidable problems, which it doesn't). So: HP is undecidable, not in NP, not NP-Hard. Common mistake! Clarify: NP-Hard problems are decidable (at least as hard as NP, which are decidable). So HP is neither NP nor NP-Hard.

VII. ADVANCED & SUPPLEMENTARY TOPICS

A. Chomsky Hierarchy of Grammars

• Inclusions: Regular ⊂ CFL ⊂ CSL ⊂ RE.

• Proper Containment: Each inclusion is proper (e.g., {aⁿ bⁿ cⁿ} is CSL but not CFL; {aⁿ} is CFL but not regular).

B. Additional Models & Problems

• Linear Bounded Automaton (LBA): TM with tape limited to length of input (plus constant). Recognizes CSL. LBA acceptance problem is undecidable.

• Petri Net Model:

  • Components: Places (circles), Transitions (rectangles), Tokens (dots).

  • Arcs connect places to transitions and vice versa.

  • Firing: Transition fires if each input place has ≥1 token; consumes one token from each input place, produces one token to each output place.

  • Application: Modeling concurrent systems, resource allocation, deadlocks.

• Two-way Finite Automata (2-DFA): Head can move left/right. Power equivalent to DFA (can be converted, but may cause exponential state blowup).

• Mathematical Induction: Used in proofs (e.g., closure properties, theorem proofs). Structure:

  1. Base case (n=0 or n=1).

  2. Inductive hypothesis (assume true for k).

  3. Inductive step (prove for k+1).

SUMMARY OF HIGH-FREQUENCY EXAM TOPICS

Final Advice: Practice conversions (NFA→DFA, RE↔FA, CFG↔CNF↔GNF, CFG↔PDA, Mealy↔Moore). For design problems (PDA, TM), start with intuitive marking/sharding strategy, then formalize transitions. For undecidability, know the standard proofs (diagonalization for A_TM, reduction for HALT_TM). For complexity, distinguish P (solvable), NP (verifiable), NPC (hardest in NP).