CS8501

Theory of Computation (ALC)

7 Files
•
CSE Department
Download Progress 0/7 files
Unit 1
Notes Not downloaded 178 KB
Unit 2
Notes Not downloaded 234 KB
Unit 3
Notes Not downloaded 151 KB
Unit 4
Notes Not downloaded 126 KB
Unit 5
Notes Not downloaded 267 KB
Important Questions
Study Not downloaded 1.5 MB
Question Paper
Exam Not downloaded 2.2 MB
Academic Study Guide

Theory of Computation & Automata Comprehensive Academic Guide

Theory of Computation establishes the mathematical foundations of computer science, formal languages, and computational complexity. This guide covers Deterministic and Non-deterministic Finite Automata (DFA/NFA), Regular Expressions, Context-Free Grammars (CFG), Pushdown Automata (PDA), Turing Machines, and the Decidability of the Halting Problem aligned with Anna University, VTU, and AICTE syllabi.

Unit-by-Unit Theoretical Revision

Unit 1: Finite Automata & Regular Languages

Finite Automata are abstract state machines with finite internal memory used for pattern matching and lexical analysis.

  • Deterministic Finite Automata (DFA): Defined as a 5-tuple (Q, Σ, δ, qâ‚€, F) where transition function δ: Q × Σ → Q maps each state and input symbol to exactly one unique next state.
  • Non-deterministic Finite Automata (NFA): Transition function δ: Q × (Σ ∪ {ε}) → 2^Q permits transitions to multiple states and spontaneous epsilon (ε) moves. DFAs and NFAs possess identical computational power: every NFA with N states can be converted to an equivalent DFA with at most 2^N states via Subset Construction (Powerset construction).
  • DFA State Minimization: Myhill-Nerode theorem and Table-Filling Algorithm (partitioning distinguishable and indistinguishable state pairs) yields the minimal unique canonical DFA.

Unit 2: Regular Expressions & Pumping Lemma for Regular Languages

  • Regular Expressions (RE): Algebraic notations defining regular languages using Union (+ or |), Concatenation (·), and Kleene Star (*). Converted to ε-NFA using Thompson’s Construction, and from DFA to RE using Arden’s Theorem (R = Q + RP → R = QP*).
  • Pumping Lemma for Regular Languages: Used to prove languages are NOT regular. If L is regular, there exists pumping length p such that any string w ∈ L with |w| ≥ p can be divided into w = xyz satisfying: (1) |y| > 0, (2) |xy| ≤ p, and (3) for all i ≥ 0, xy^i z ∈ L. (Classical contradiction applied to L = {0^n 1^n | n ≥ 0}).
  • Closure Properties of Regular Languages: Closed under Union, Intersection, Complement, Concatenation, Kleene Star, Difference, Reversal, and Homomorphism.

Unit 3: Context-Free Grammars & Languages (CFG / CFL)

  • Context-Free Grammar (CFG): 4-tuple (V, T, P, S) where production rules have form A → α with A ∈ V (single non-terminal) and α ∈ (V ∪ T)*.
  • Ambiguity: A grammar is ambiguous if there exists at least one string possessing two or more distinct leftmost derivations, rightmost derivations, or parse trees. Inherent ambiguity occurs when a CFL has no unambiguous grammar.
  • Normal Forms for CFG:
    • Chomsky Normal Form (CNF): All productions of form A → BC or A → a. Parse tree for string of length n has exactly 2n - 1 internal steps. Used in the CYK parsing algorithm.
    • Greibach Normal Form (GNF): All productions of form A → aα where a ∈ T and α ∈ V*.
  • Pumping Lemma for CFLs: Any string z ∈ L with |z| ≥ p decomposes into uvwxy such that |vwx| ≤ p, |vx| ≥ 1, and uv^i wx^i y ∈ L for all i ≥ 0. Proves {a^n b^n c^n | n ≥ 0} is not context-free.

Unit 4: Pushdown Automata (PDA)

A Pushdown Automaton extends a finite automaton with an auxiliary infinite LIFO Stack memory.

  • PDA 7-Tuple: (Q, Σ, Γ, δ, qâ‚€, zâ‚€, F) where Γ is stack alphabet and δ: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*).
  • Acceptance Modes: Acceptance by Final State (T(M)) vs Acceptance by Empty Stack (N(M)). Both forms are computationally equivalent.
  • Deterministic PDA (DPDA) vs NPDA: Unlike finite automata, NPDAs are strictly more powerful than DPDAs. DPDAs recognize Deterministic Context-Free Languages (DCFLs), which form the foundation of unambiguous programming language parsers (LR parsers). NPDAs recognize all CFLs (including palindromes like ww^R).

Unit 5: Turing Machines, Chomsky Hierarchy & Undecidability

  • Turing Machine (TM): 7-tuple (Q, Σ, Γ, δ, qâ‚€, B, F) with an infinite read/write tape and bidirectional read/write head. Universal computational model embodying the Church-Turing Thesis.
  • Chomsky Hierarchy:
    • Type 3 (Regular): Recognized by Finite Automata. Rule: A → aB or A → a.
    • Type 2 (Context-Free): Recognized by Pushdown Automata. Rule: A → α.
    • Type 1 (Context-Sensitive): Recognized by Linear Bounded Automata (LBA). Rule: αAβ → αγβ with |γ| ≥ |A|.
    • Type 0 (Recursively Enumerable): Recognized by Turing Machines. Unrestricted production rules.
  • Decidability & The Halting Problem: A language is Decidable (Recursive) if a TM halts and accepts valid strings and halts and rejects invalid strings. Alan Turing proved that determining whether an arbitrary Turing machine will halt on a given input string is mathematically Undecidable (proof via diagonalization/contradiction).
  • Post Correspondence Problem (PCP): Classic undecidable problem regarding string tile matching.

Chomsky Hierarchy Summary Matrix

Type Language Class Automaton / Machine Production Rule Form Closed Under Complement?
Type 3RegularFinite Automaton (DFA / NFA)A → aB or A → aYes
Type 2Context-FreePushdown Automaton (NPDA)A → αNo (Only DCFLs are)
Type 1Context-SensitiveLinear Bounded Automaton (LBA)αAβ → αγβ (|γ| ≥ |A|)Yes
Type 0Recursively EnumerableTuring Machineα → β (unrestricted)No (Recursive are, RE are not)

High-Frequency University Exam Questions

Q1: Prove that L = {0^n 1^n | n ≥ 1} is not a regular language using the Pumping Lemma.

Assume L is regular with pumping length p. Choose string w = 0^p 1^p ∈ L with length |w| = 2p ≥ p. According to the Pumping Lemma, w = xyz where |xy| ≤ p and |y| ≥ 1. Because |xy| ≤ p, substring y must consist entirely of 0s (say y = 0^k where k ≥ 1). Pumping with i = 2 yields xy²z = 0^(p+k) 1^p. Since p + k ≠ p, the number of 0s does not equal the number of 1s, so xy²z ∉ L, contradicting the lemma. Hence, L is not regular.

Q2: Explain the significance of Chomsky Normal Form (CNF) and write its production constraints.

In Chomsky Normal Form, every production rule must be strictly in one of two formats: (1) A → BC (where A, B, C are non-terminals, with B and C not being the start symbol), or (2) A → a (where a is a terminal). CNF standardizes grammar structures, guarantees binary parse trees, bounds derivation length to exactly 2n - 1 steps for any string of length n, and enables dynamic programming parsing algorithms such as the CYK algorithm in O(n³ · |G|) time.

Q3: State the Halting Problem of Turing Machines and explain why it is undecidable.

The Halting Problem asks: Given a description of an arbitrary Turing machine M and an input w, does M halt on w? Alan Turing proved that no algorithm can solve this problem for all pairs (M, w). The proof proceeds by contradiction using diagonalization: Assume there exists a decider H that outputs YES if M halts on w, and NO otherwise. Construct a new machine D that takes the description of a machine M, calls H(M, M), and intentionally loops infinitely if H says YES, or halts immediately if H says NO. Running D on its own description D leads to a logical paradox: D halts if and only if D does not halt. Thus, such a decider H cannot exist, proving the problem undecidable.