UNIT 3: Theory of Computation – Comprehensive Short Notes

I. Finite Automata (FA)

Deterministic Finite Automata (DFA)

Definition: A DFA is a 5-tuple $$\displaystyle M = (Q, \Sigma, \delta, q_0, F) $$ where:
- $Q$: finite set of states
- $\Sigma$: finite input alphabet
- $$\displaystyle \delta: Q \times \Sigma \rightarrow Q $$: transition function
- $$\displaystyle q_0 \in Q $$: start state
- $F \subseteq Q$: set of final/accepting states
Operation: On reading input symbol $a$ in state $q$, moves to $\delta(q,a)$. No ε-transitions.

Example: DFA for strings over $\{0,1\}$ ending with "01":


[[DIAGRAM: CANVAS: DFA with states q0 (start), q1, q2 (final). 

q0--0-->q0, q0--1-->q1; 

q1--0-->q2, q1--1-->q1; 

q2--0-->q0, q2--1-->q1]]

Non-deterministic Finite Automata (NFA)

Definition: NFA is a 5-tuple $$\displaystyle M = (Q, \Sigma, \delta, q_0, F) $$ where:
- $$\displaystyle \delta: Q \times (\Sigma \cup \{\epsilon\}) \rightarrow \mathcal{P}(Q) $$: transition to set of states
- ε-transitions allowed (move without consuming input)
Key Difference: DFA has exactly one transition per state-symbol pair; NFA can have multiple or none.

Example: NFA for language containing "ab" as substring:


[[DIAGRAM: CANVAS: NFA with q0 (start), q1, q2 (final). 

q0--ε-->q1, q0--a-->q1; 

q1--b-->q2; 

q2--any-->q2 (loop)]]

Equivalence and Conversions

Equivalence: DFA and NFA recognize the same class of languages (regular languages).
Subset Construction (NFA → DFA):
- DFA states = subsets of NFA states.
- Start state = ε-closure($$\displaystyle q_0 $$).
- $$\displaystyle \delta_{DFA}(S, a) = \bigcup_{q \in S} \delta_{NFA}(q, a) $$ (then take ε-closure).
ε-closure: Set of states reachable via ε-transitions from a given state.

[!TIP] Exam Focus: Subset construction can cause exponential state blowup. Always compute ε-closure first when converting ε-NFA to NFA.

Minimization of DFA

Goal: Remove equivalent (indistinguishable) states.
Algorithm: Partition refinement.
1. Initial partition: $F$ and $Q \setminus F$.
2. Refine: Split partitions where states have different transitions to other partitions.
3. Repeat until stable.
Result: Unique minimal DFA (up to renaming).

Finite Automata with Outputs

Mealy Machine: Output depends on current state and input.
- Components: $$\displaystyle (Q, \Sigma, \Delta, \delta, \lambda, q_0) $$ where $$\displaystyle \lambda: Q \times \Sigma \rightarrow \Delta $$ (output alphabet).
Moore Machine: Output depends only on current state.
- $$\displaystyle \lambda: Q \rightarrow \Delta $$.
Conversion:
- Mealy → Moore: Split states with different outputs on same input.
- Moore → Mealy: Output on entering state.

Composite Machines

Series Connection: Output of first machine feeds as input to second. Language = $$\displaystyle L_1 \cdot L_2 $$.
Parallel Connection: Both machines process same input; final state if both accept. Language = $$\displaystyle L_1 \cap L_2 $$.

II. Regular Languages and Expressions

Regular Expressions (RE)

Definition: Built from $\emptyset$, $\epsilon$, symbols $a \in \Sigma$ using:
- Union: $$\displaystyle r_1 + r_2 $$
- Concatenation: $$\displaystyle r_1 r_2 $$
- Kleene star: $$\displaystyle r^* $$
Examples:
- Strings ending with "ab": $$\displaystyle (a+b)^*ab $$
- Exactly two a's: $$\displaystyle b^*ab^*ab^* $$
- Length divisible by 3: $$\displaystyle (aaa)^* $$

Equivalence of RE and FA

Thompson’s Construction (RE → NFA):
- Base: ε, ∅, $a$ → simple NFA.
- Recursive: Union (new start with ε to both), concatenation (connect), star (new start/end with loops).
State Elimination (DFA → RE):
1. Add new start/final states with ε-transitions.
2. Eliminate states one by one, updating edge labels with RE.
3. Final RE = label from new start to new final.

Arden’s Theorem

Statement: For RE equations $$\displaystyle X = AX + B $$, the solution is $$\displaystyle X = A^*B $$ (if $\epsilon \notin A$).
Application: Solve system of linear equations for DFA states.
- Write equations: $$\displaystyle q_i = \sum \delta(q_i, a) \cdot a + \text{if } q_i \in F \text{ then } \epsilon $$.
- Solve recursively from start state.

[!TIP] Common Pitfall: Ensure no left-recursion in equations; Arden’s requires $A$ not containing $\epsilon$ for the standard form.

Closure Properties of Regular Languages

Regular languages are closed under:

Union, intersection, complement, concatenation, Kleene star, reversal, homomorphism, inverse homomorphism, substitution.
Proofs: Use automata constructions (product for intersection, complement by swapping final/non-final, etc.).

Pumping Lemma for Regular Languages

Statement: If $L$ is regular, ∃ pumping length $p \geq 1$ such that ∀ $w \in L$ with $|w| \geq p$, $$\displaystyle w = xyz $$ with:
1. $$\displaystyle |y| > 0 $$
2. $|xy| \leq p$
3. $$\displaystyle xy^iz \in L $$ for all $i \geq 0$.
Application: To prove non-regularity, assume regular, choose $w$, show no split satisfies condition.
Example: $$\displaystyle L = \{a^n b^n \mid n \geq 0\} $$ is not regular (choose $$\displaystyle w = a^p b^p $$).

Regular Grammars

Right-linear: $$\displaystyle A \rightarrow aB $$ or $$\displaystyle A \rightarrow a $$ or $$\displaystyle A \rightarrow \epsilon $$.
Left-linear: $$\displaystyle A \rightarrow Ba $$ or $$\displaystyle A \rightarrow a $$ or $$\displaystyle A \rightarrow \epsilon $$.
Equivalence: Right-linear grammars generate exactly regular languages (equivalent to DFA).

III. Context-Free Grammars (CFG) and Languages

CFG Fundamentals

Definition: $$\displaystyle G = (V, T, P, S) $$ where:
- $V$: variables (non-terminals)
- $T$: terminals
- $P$: productions $$\displaystyle A \rightarrow \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 each step.
Parse Tree (Derivation Tree): Root = $S$, leaves = terminals (in order = yield), internal nodes = variables.

Ambiguity in CFG

Definition: A string has two or more distinct parse trees (or leftmost/rightmost derivations).
Classic Example: "Dangling else":
```
S → if S else S | if S | other
```
String "if a then if b then c else d" has two parses.
Removal Methods:
- Grammar rewriting (introduce precedence).
- Use unambiguous grammar (e.g., match each else with nearest if).

Normal Forms

Chomsky Normal Form (CNF):
- Productions: $$\displaystyle A \rightarrow BC $$ (both variables) or $$\displaystyle A \rightarrow a $$ (terminal), or $$\displaystyle S \rightarrow \epsilon $$ (if $\epsilon \in L$).
- Conversion Steps:
  1. Eliminate ε-productions (except possibly $$\displaystyle S \rightarrow \epsilon $$).
  2. Eliminate unit productions ($$\displaystyle A \rightarrow B $$).
  3. Eliminate useless symbols.
  4. Convert to binary: $$\displaystyle A \rightarrow BCD $$ → $$\displaystyle A \rightarrow BE $$, $$\displaystyle E \rightarrow CD $$.
Greibach Normal Form (GNF):
- $$\displaystyle A \rightarrow a\alpha $$ where $a \in T$, $$\displaystyle \alpha \in V^* $$ (no ε).
- Conversion: Order variables, eliminate left recursion recursively.

Closure Properties of CFLs

Closed: Union, concatenation, Kleene star, substitution, reversal.
Not Closed: Intersection, complement.
- Example: $$\displaystyle L_1 = \{a^n b^n c^m\} $$, $$\displaystyle L_2 = \{a^m b^n c^n\} $$ are CFLs but $$\displaystyle L_1 \cap L_2 = \{a^n b^n c^n\} $$ is not CFL.

Pumping Lemma for CFLs

Statement: If $L$ is CFL, ∃ $p \geq 1$ such that ∀ $w \in L$ with $|w| \geq p$, $$\displaystyle w = uvxyz $$ with:
1. $$\displaystyle |vy| > 0 $$
2. $|vxy| \leq p$
3. $$\displaystyle uv^ixy^iz \in L $$ for all $i \geq 0$.
Application: Choose $w$ strategically (often $$\displaystyle w = a^p b^p c^p $$ for $$\displaystyle \{a^n b^n c^n\} $$).

Decision Properties

Membership: CYK algorithm (O($$\displaystyle n^3 $$)) for CFG in CNF.
Emptiness: Check if start symbol can derive a terminal string.
Finiteness: Remove ε, unit, useless; check for cycles in dependency graph.

IV. Pushdown Automata (PDA)

PDA 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 \{\epsilon\}) \times \Gamma \rightarrow \mathcal{P}(Q \times \Gamma^*) $$: transition
- $$\displaystyle q_0 $$: start state
- $$\displaystyle Z_0 $$: 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 contents (top first).

Acceptance Modes

By final state: Accept if after reading entire input, $q \in F$ (stack can be anything).
By empty stack: Accept if stack becomes empty (input may be exhausted or not, but typically we require input exhausted too).
Equivalence: For any PDA, can construct another with same language by switching modes (but not for DPDA).

Deterministic vs. Non-deterministic PDA

DPDA: At most one transition for any $(q, a, A)$ (where $a \in \Sigma \cup \{\epsilon\}$). If ε-transition exists, no other transition on same input.
DCFL: Languages accepted by DPDA (by final state or empty stack).
Example: $$\displaystyle \{a^n b^n\} $$ is DCFL; $$\displaystyle \{a^n b^n c^n\} $$ is not CFL; $$\displaystyle \{ww^R\} $$ is CFL but not DCFL? Actually $$\displaystyle \{ww^R\} $$ is DCFL? No, it is not DCFL because DPDA cannot compare two halves without knowing midpoint. Actually $$\displaystyle \{ww^R\} $$ is not DCFL (requires non-determinism to guess midpoint). But $$\displaystyle \{a^n b^n\} $$ is DCFL.

Design of PDA

General Strategy:
- For $$\displaystyle a^n b^n $$: Push $a$'s, pop on $b$'s.
- For palindromes $$\displaystyle ww^R $$: Non-deterministically guess midpoint, push first half, pop on second half.
- For balanced parentheses: Push opening, pop on matching closing.

Example PDA for $$\displaystyle L = \{a^n b^n \mid n \geq 1\} $$ (by final state):


States: {q0, q1, q2}

Start: q0, Stack: Z0

Transitions:

  δ(q0, a, Z0) = {(q0, AZ0)}   // push A

  δ(q0, a, A) = {(q0, AA)}     // push more A

  δ(q0, b, A) = {(q1, ε)}      // start popping

  δ(q1, b, A) = {(q1, ε)}      // continue popping

  δ(q1, ε, Z0) = {(q2, Z0)}   // accept when stack back to Z0

Final state: q2

Conversion between CFG and PDA

CFG → PDA (standard construction):
- PDA simulates leftmost derivation.
- Stack holds current sentential form (variables and terminals).
- Transitions: For $$\displaystyle A \rightarrow \alpha $$, pop $A$, push $\alpha$ (in reverse order).
- Acceptance by empty stack.
PDA → CFG:
- For each pair of states $(p, q)$, create variable $[p,q]$ generating strings that take PDA from $p$ to $q$ with stack unchanged except possibly popping $p$'s symbol and pushing $q$'s.
- Detailed: For transition $\delta(r, a, A) \ni (s, BC)$, add $$\displaystyle [p,q] \rightarrow a[r,s][s,q] $$ etc.

V. Turing Machines (TM)

TM Definition and Model

Components: $$\displaystyle M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject}) $$ where:
- $Q$: states
- $\Sigma$: input alphabet (no blank symbol ␣)
- $\Gamma \supseteq \Sigma \cup \{\sqcup\}$: tape alphabet (␣ = blank)
- $$\displaystyle \delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\} $$: transition
- $$\displaystyle q_0 $$: start state
- $$\displaystyle q_{accept}, q_{reject} $$: halting states (distinct).
Instantaneous Description: $(q, u \sqcup v)$ where $u$ = left of head, $v$ = under head and right.

Construction Techniques

Basic Building Blocks:
- Scanning: Move right/left until a symbol is found.
- Marking: Change symbol to mark it (e.g., $$\displaystyle a \rightarrow X $$).
- Shifting: Move entire tape content left/right.
- Copying: Copy substring to another part of tape.
Design Examples:
1. Even number of 1's:
  - States: $$\displaystyle q_0 $$ (even), $$\displaystyle q_1 $$ (odd). On 1, switch state; on 0, stay. Accept in $$\displaystyle q_0 $$.
2. $$\displaystyle a^n b^n $$:
  - Cross off one $a$ and one $b$ repeatedly.
3. $$\displaystyle a^n b^n c^n $$:
  - Mark $a$, then find corresponding $b$ and $c$.
4. Multiplication: Repeated addition (add $b$'s $a$ times).

Multi-tape TM

Definition: Multiple tapes, each with own head. Transition: $$\displaystyle \delta: Q \times \Gamma^k \rightarrow Q \times \Gamma^k \times \{L,R,S\}^k $$.
Equivalence: Can simulate multi-tape TM with single-tape TM (use delimiters and track multiple tracks).

Non-deterministic TM

Definition: $$\displaystyle \delta: Q \times \Gamma \rightarrow \mathcal{P}(Q \times \Gamma \times \{L,R\}) $$.
Equivalence: NTM = TM (can simulate all branches in dovetailing fashion).

Universal Turing Machine

Concept: A TM that simulates any other TM given its description and input.
Significance: Foundation of stored-program computers; shows existence of general-purpose machine.
Construction Sketch:
1. Encode TM as string (states, tape alphabet, transition table).
2. UTM reads description, simulates step-by-step, maintaining simulated tape on its own tape.

VI. Undecidability and Reducibility

Halting Problem

Statement: $$\displaystyle HALT_{TM} = \{\langle M, w \rangle \mid M \text{ halts on } w\} $$ is undecidable.
Proof (reduction from $$\displaystyle A_{TM} $$):
- Assume $$\displaystyle HALT_{TM} $$ decidable by $H$.
- Construct $D$ that on $\langle M, w \rangle$:
  1. Run $H$ on $\langle M, w \rangle$.
  2. If $H$ rejects (doesn’t halt), accept.
  3. If $H$ accepts (halts), loop.
- Then $D$ decides $$\displaystyle A_{TM} $$? Contradiction.

Post Correspondence Problem (PCP)

Definition: Given set of dominoes $$\displaystyle \{(x_i, y_i)\}_{i=1}^n $$, find sequence $$\displaystyle i_1, ..., i_k $$ such that $$\displaystyle x_{i_1}...x_{i_k} = y_{i_1}...y_{i_k} $$.
Example: $\{(b, bab), (a, ab), (ba, ba)\}$ → solution: $b, a, ba, a$ gives $$\displaystyle baba = baba $$.
Undecidability: Reduce from $$\displaystyle A_{TM} $$.

Rice’s Theorem

Statement: Any non-trivial property of RE languages is undecidable.
- Non-trivial: Some RE languages have it, some don’t.
Application:
- "Is $L(M)$ regular?" → undecidable.
- "Is $L(M)$ finite?" → undecidable.
- "Does $M$ accept any string?" → undecidable (emptiness problem for TM).

Undecidable Problems

Examples:
- $$\displaystyle A_{TM} = \{\langle M, w \rangle \mid M \text{ accepts } w\} $$ (undecidable but RE).
- $$\displaystyle E_{TM} = \{\langle M \rangle \mid L(M) = \emptyset\} $$ (undecidable).
- $$\displaystyle REGULAR_{TM} = \{\langle M \rangle \mid L(M) \text{ is regular}\} $$ (undecidable by Rice).

VII. Complexity Theory

Complexity Classes

P: Languages decidable by deterministic TM in polynomial time.
- Examples: PATH, SORTING, 2-SAT.
NP: Languages decidable by non-deterministic TM in polynomial time, or: solutions verifiable in polynomial time.
- Examples: SAT, CLIQUE, VERTEX COVER, HAMILTONIAN CYCLE.
Relationship: $P \subseteq NP$. $$\displaystyle P = NP? $$ (open problem).

NP-Completeness

Definition: $L$ is NP-complete if:
1. $L \in NP$.
2. ∀ $L' \in NP$, $$\displaystyle L' \leq_p L $$ (polynomial-time reducible).
Cook-Levin Theorem: SAT is NP-complete.
Reduction Technique: To show $L$ NP-complete:
1. Show $L \in NP$.
2. Reduce known NP-complete problem (e.g., 3-SAT) to $L$.
Examples:
- 3-SAT: SAT where each clause has 3 literals.
- Clique: Given graph $G$, integer $k$, is there a clique of size $k$?
- Vertex Cover: Given $G$, $k$, is there a vertex cover of size $k$?
- Hamiltonian Cycle: Does $G$ have a cycle visiting each vertex once?

P vs NP Problem

Significance: If $$\displaystyle P = NP $$, all NP problems have efficient algorithms; if $P \neq NP$, some NP problems are inherently hard.
Implications: Cryptography relies on $P \neq NP$ assumption.

co-NP and Other Classes

co-NP: Complements of NP languages. If $L \in NP$, then $\overline{L} \in co-NP$.
Question: Is $$\displaystyle NP = co-NP $$? (Unknown, but if $$\displaystyle P = NP $$ then yes).
Other Classes: PSPACE, EXPTIME, BPP (probabilistic).

VIII. Advanced Topics and Models

Chomsky Hierarchy


Type 0: Unrestricted grammars (RE languages)

Type 1: Context-sensitive grammars (CSL, LBA)

Type 2: Context-free grammars (CFL, PDA)

Type 3: Regular grammars (regular, FA)

Relationships: Regular ⊂ CFL ⊂ CSL ⊂ RE.
Examples:
- Type 3: $$\displaystyle a^* b^* $$
- Type 2: $$\displaystyle a^n b^n $$
- Type 1: $$\displaystyle a^n b^n c^n $$ (CSL but not CFL)
- Type 0: $$\displaystyle \{a^n b^n c^n d^n\} $$ (RE but not CSL? Actually not CSL either? It’s not RE? It is RE but not CSL? Actually $$\displaystyle a^n b^n c^n d^n $$ is not CSL? It is not context-sensitive? It is context-sensitive? Actually it is not context-sensitive because it requires more than linear space? It is not CSL? Actually it is not CSL because it is not accepted by LBA? It is not in CSL? Actually it is in CSL? Wait: CSL = languages accepted by LBA. LBA can count with linear space. $$\displaystyle a^n b^n c^n d^n $$ requires counting 4 counters, which can be done in linear space? Yes, LBA can do it. So it is CSL. But it is not CFL. So it is Type 1 but not Type 2.)

Two-way Finite Automata (2-DFA/2-NFA)

Model: FA that can move left or right on tape.
Equivalence: 2-DFA = DFA (same power), 2-NFA = NFA (same power).
Closure: Regular languages closed under 2-way operations.

Petri Nets

Components:
- Places (circles), Transitions (bars), Tokens (dots).
- Directed arcs from places to transitions and transitions to places.
Firing: Transition fires if each input place has at least one token; consumes one token from each input place, produces one token in each output place.
Applications: Modeling concurrent systems, synchronization, resource allocation.

Linear Bounded Automata (LBA)

Definition: TM where tape is limited to the region containing input (plus bounded extra).
Equivalence: Accepts exactly context-sensitive languages (Type 1) except possibly $\epsilon$.
Difference from TM: LBA tape is linearly bounded; TM has infinite tape.

IX. Problem-Solving Techniques and Miscellaneous

Mathematical Induction

Basis: Prove for $$\displaystyle n=0 $$ or $$\displaystyle n=1 $$.
Inductive Step: Assume true for $$\displaystyle n=k $$, prove for $$\displaystyle n=k+1 $$.
Application: Proving properties of automata, grammars, language inclusions.

Closure Properties Proofs

Regular Languages: Use automata constructions.
- Union: Product construction with final states as union.
- Intersection: Product with final states where both are final.
- Complement: Swap final/non-final.
CFLs: Use grammar constructions (union: add new start with productions to both starts; concatenation: new start → $$\displaystyle S_1 S_2 $$; star: $$\displaystyle S \rightarrow SS \mid \epsilon $$).
Recursive Languages: Use decider constructions (simulate both deciders in sequence for union, etc.).

Pumping Lemma Applications

Regular Languages:
1. Assume $L$ regular, let $p$ = pumping length.
2. Choose $w \in L$, $|w| \geq p$.
3. Write $$\displaystyle w = xyz $$ with conditions.
4. Show ∃ $i$ such that $$\displaystyle xy^iz \notin L $$.
CFLs:
1. Assume $L$ CFL, let $p$ = pumping length.
2. Choose $w \in L$, $|w| \geq p$.
3. Write $$\displaystyle w = uvxyz $$ with $|vxy| \leq p$, $$\displaystyle |vy| > 0 $$.
4. Show ∃ $i$ such that $$\displaystyle uv^ixy^iz \notin L $$.
Key: Choose $w$ that forces overlapping parts (e.g., $$\displaystyle a^p b^p c^p $$ for CFL).

Designing Automata

Systematic Approach:
1. Understand language description.
2. Identify key patterns (prefixes, suffixes, counts, matching).
3. Sketch states for important conditions.
4. Add transitions, including dead state if needed.
5. Minimize if required.

Conversions Between Representations

RE ↔ FA: Thompson (RE→NFA) and state elimination (DFA→RE).
CFG ↔ PDA: Standard constructions (CFG→PDA by leftmost derivation simulation; PDA→CFG by variables for state pairs).
Mealy ↔ Moore:
- Mealy→Moore: For each state with multiple outputs on same input, split into multiple states.
- Moore→Mealy: Output on entering state can be placed on transitions entering that state.
ε-NFA ↔ NFA: Compute ε-closure for each state; for each symbol, take union of ε-closures of NFA transitions.

Solving PCP

Method:
1. Try to match top strings.
2. Use dominoes that extend match.
3. Look for cycles that can be repeated.
Example: Given dominoes, build match incrementally. If no solution found after reasonable steps, may be undecidable.

Parsing and Ambiguity Resolution

Role of Derivations: Leftmost/rightmost derivations correspond to parsing orders.
Detecting Ambiguity: Find string with two distinct parse trees.
Resolution:
- Introduce precedence (e.g., if-then-else).
- Rewrite grammar (e.g., factor common prefixes).
- Use operator precedence grammars.

\boxed{\text{These notes cover all topics from UNIT 3 as per blueprint and past papers.}}