Tutorials

Theory of Computation - Complete Tutorial Guide

This tutorial provides comprehensive practice problems, exam-style questions, and review materials covering all three units of Theory of Computation.

Unit 1: Regular Languages & Finite Automata

Tutorial 1.1: Finite Automata Design

Q1: Design DFA accepting strings with even number of 0’s and odd number of 1’s.

Solution:

States: {q₀₀, q₀₁, q₁₀, q₁₁}
q₀₀ = even 0's, even 1's (start)
q₀₁ = even 0's, odd 1's (accept)
q₁₀ = odd 0's, even 1's
q₁₁ = odd 0's, odd 1's

Transitions:
δ(q₀₀, 0) = q₁₀
δ(q₀₀, 1) = q₀₁
δ(q₀₁, 0) = q₁₁
δ(q₀₁, 1) = q₀₀
δ(q₁₀, 0) = q₀₀
δ(q₁₀, 1) = q₁₁
δ(q₁₁, 0) = q₀₁
δ(q₁₁, 1) = q₁₀

Q2: Design NFA accepting strings ending with “01”.

Solution:

States: {q₀, q₁, q₂}
Start: q₀
Accept: {q₂}

δ(q₀, 0) = {q₀, q₁}
δ(q₀, 1) = {q₀}
δ(q₁, 1) = {q₂}

Q3: Convert NFA to DFA for language {w | w contains “ab”}.

Solution: Use subset construction, create states for all possible NFA state combinations.

Tutorial 1.2: Regular Expressions

Q1: Write regular expression for strings with at least two a’s.

Answer: babab*

Q2: Convert (a|b)*abb to ε-NFA.

Solution: Use Thompson’s construction.

Q3: Are these equivalent? (a|b)* and a*b*

Answer: No! First accepts “ab”, second doesn’t.

Tutorial 1.3: Pumping Lemma

Q1: Prove {0ⁿ1ⁿ | n ≥ 0} not regular.

Proof:

1. Assume regular, let p be pumping length
2. Choose w = 0ᵖ1ᵖ, |w| = 2p ≥ p
3. By pumping lemma, w = xyz where |xy| ≤ p, |y| ≥ 1
4. So xy consists only of 0’s
5. Pump: xy²z = 0ᵖ⁺|y|1ᵖ
6. Different number of 0’s and 1’s - not in language!
7. Contradiction, so not regular.

Q2: Prove {ww | w ∈ {a,b}*} not regular.

Proof: Use pumping lemma with w = aᵖbaᵖb.

Q3: Is {aⁱbʲ | i ≥ j} regular?

Answer: No! Use pumping lemma.

Unit 2: Context-Free Languages & Pushdown Automata

Tutorial 2.1: Context-Free Grammars

Q1: Design CFG for {aⁿbⁿ | n ≥ 0}.

Solution:

S → aSb | ε

Q2: Design CFG for balanced parentheses.

Solution:

S → SS | (S) | ε

Q3: Show derivation for “aabb” in {aⁿbⁿ} grammar.

Solution:

S ⇒ aSb ⇒ aaSbb ⇒ aabb

Tutorial 2.2: Chomsky Normal Form

Q1: Convert to CNF:

S → ASB | ε
A → aAS | a
B → SbS | A | bb

Solution:

1. Add S₀ → S (new start)
2. Remove ε-productions
3. Remove unit productions
4. Convert to A → BC or A → a form

Q2: Use CYK to parse “aabb” with CNF grammar.

Solution: Build parse table bottom-up.

Tutorial 2.3: Pushdown Automata

Q1: Design PDA for {aⁿbⁿ | n ≥ 0}.

Solution:

1. Push a's onto stack
2. Pop for each b
3. Accept if stack empty

δ(q₀, a, Z₀) = (q₀, AZ₀)
δ(q₀, a, A) = (q₀, AA)
δ(q₀, b, A) = (q₁, ε)
δ(q₁, b, A) = (q₁, ε)
δ(q₁, ε, Z₀) = (qaccept, Z₀)

Q2: Design PDA for {wcwᴿ | w ∈ {a,b}*}.

Solution: Push w, see c, pop and compare.

Q3: Convert CFG S → aSb | ε to PDA.

Solution: Use standard conversion (single state, simulate leftmost derivation).

Tutorial 2.4: Pumping Lemma for CFLs

Q1: Prove {aⁿbⁿcⁿ | n ≥ 0} not context-free.

Proof:

1. Assume CFL, let p be pumping length
2. Choose w = aᵖbᵖcᵖ
3. w = uvxyz where |vxy| ≤ p, |vy| ≥ 1
4. vxy contains at most 2 symbol types
5. Pumping changes at most 2 counts, third unchanged
6. Violates equality - contradiction!

Q2: Prove {ww | w ∈ {a,b}*} not context-free.

Proof: Choose w = aᵖbaᵖb, pumping destroys ww pattern.

Q3: Is {aⁿb²ⁿ | n ≥ 0} context-free?

Answer: Yes! Grammar: S → aSbb | ε

Unit 3: Turing Machines & Complexity

Tutorial 3.1: Turing Machine Design

Q1: Design TM for {0ⁿ1ⁿ | n ≥ 0}.

Solution:

1. Mark leftmost 0 with X
2. Scan right to first 1, mark with Y
3. Return to start
4. Repeat until all matched
5. Accept if all marked correctly

Q2: Design TM for {aⁿbⁿcⁿ | n ≥ 0}.

Solution: Mark one of each (a,b,c) repeatedly until all matched.

Q3: Trace execution of {0ⁿ1ⁿ} TM on input “0011”.

Solution: Show step-by-step configuration changes.

Tutorial 3.2: Decidability

Q1: Is {⟨M⟩ | M accepts at least one string} decidable?

Answer: No! Undecidable by Rice’s theorem (non-trivial property).

Q2: Is {⟨M⟩ | M has 5 states} decidable?

Answer: Yes! Syntactic property, can check encoding.

Q3: Prove acceptance problem A_TM undecidable.

Solution: Reduce from HALT or use diagonalization.

Tutorial 3.3: Complexity Theory

Q1: Show sorting is in P.

Solution: Merge sort runs in O(n log n) = polynomial.

Q2: Show SAT is in NP.

Solution:

• Certificate: Variable assignment
• Verifier: Plug values, evaluate (polynomial time)

Q3: What is time complexity of:

for i = 1 to n:
  for j = 1 to i:
    for k = 1 to j:
      do O(1) work

Answer: O(n³)

Comprehensive Practice Problems

Problem Set 1: Automata

1. Design DFA for strings with substring “101”
2. Convert NFA with ε-transitions to DFA
3. Minimize given DFA using equivalence classes
4. Prove language not regular using pumping lemma
5. Write regular expression for “all strings except those containing aa”

Problem Set 2: Grammars

1. Design CFG for palindromes over {a,b}
2. Show grammar is ambiguous with example
3. Convert CFG to Chomsky Normal Form
4. Convert CFG to Greibach Normal Form
5. Remove left recursion from grammar

Problem Set 3: PDAs

1. Design PDA accepting by empty stack for {aⁿbⁿ}
2. Convert PDA to CFG
3. Prove language requires PDA (not regular)
4. Design PDA for {aⁱbʲcᵏ | i = j or j = k}
5. Compare DPDA vs NPDA with examples

Problem Set 4: Turing Machines

1. Design TM for {ww | w ∈ {a,b}*}
2. Design TM for prime numbers {aᵖ | p prime}
3. Show multi-tape TM more efficient than single-tape
4. Design Universal TM (conceptual)
5. Prove variant of TM equivalent to standard

Problem Set 5: Decidability

1. Prove halting problem undecidable
2. Show problem undecidable using reduction
3. Apply Rice’s theorem to prove undecidability
4. Distinguish decidable from recognizable
5. Prove language not even recognizable

Problem Set 6: Complexity

1. Analyze time complexity of algorithms
2. Show problem is in P with algorithm
3. Prove problem is NP-complete
4. Design polynomial-time reduction
5. Compare space vs time complexity

Exam-Style Questions

Short Answer Questions (5 marks each)

1. Define DFA formally and give example
2. State and explain pumping lemma for regular languages
3. What is difference between PDA and DPDA?
4. Define Turing Machine with all components
5. Explain Church-Turing thesis
6. What is halting problem? Why undecidable?
7. Define P and NP complexity classes
8. What are NP-complete problems?

Long Answer Questions (10 marks each)

1. Design DFA for given language and prove correctness
2. Convert CFG to CNF showing all steps
3. Design PDA and show acceptance trace
4. Design TM and trace execution on example input
5. Prove language not regular using pumping lemma
6. Prove halting problem undecidable (complete proof)
7. Prove problem is NP-complete using reduction
8. Compare complexity classes P, NP, PSPACE

Important Theorems to Remember

Unit 1

1. NFA = DFA in power
2. Regular expressions = FA
3. Pumping lemma for regular languages
4. Myhill-Nerode theorem
5. Closure properties of regular languages

Unit 2

1. PDA = CFG in power
2. Pumping lemma for CFLs
3. CFLs closed under union, concat, star
4. CFLs NOT closed under intersection, complement
5. CYK parsing algorithm O(n³)

Unit 3

1. Church-Turing thesis
2. Halting problem undecidable
3. Rice’s theorem
4. Every NTM has equivalent DTM
5. Multi-tape = single-tape (simulation)
6. Savitch’s theorem: NSPACE(f) ⊆ DSPACE(f²)
7. Time hierarchy theorem
8. Space hierarchy theorem
9. Cook-Levin theorem (SAT NP-complete)

Quick Reference

Language Hierarchy

Regular Languages
    ⊂
Context-Free Languages
    ⊂
Context-Sensitive Languages (DSPACE(n))
    ⊂
Recursive (Decidable) Languages
    ⊂
Recursively Enumerable Languages
    ⊂
All Languages

Complexity Hierarchy

L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME

Known:
- P ⊊ EXPTIME (strict)
- L ⊊ PSPACE (strict)

Unknown:
- P vs NP
- NP vs PSPACE
- L vs NL

Closure Properties

Decision Problems

Exam Tips

Unit 1 Tips

1. Practice drawing state diagrams
2. Master subset construction (NFA → DFA)
3. Memorize pumping lemma proof structure
4. Know closure properties with proofs
5. Practice regular expression conversions

Unit 2 Tips

1. Understand derivation types (leftmost, rightmost)
2. Master CNF conversion steps
3. Practice PDA design with stack operations
4. Know when to use pumping lemma for CFLs
5. Understand why some languages not CFL

Unit 3 Tips

1. Practice TM design with detailed traces
2. Master reduction technique for undecidability
3. Know Rice’s theorem applications
4. Understand complexity class relationships
5. Practice NP-completeness proofs

General Tips

1. Draw diagrams whenever possible
2. Show all steps in conversions
3. Provide examples and counterexamples
4. State theorems before using them
5. Check your proofs for completeness

Common Mistakes to Avoid

1. ✗ Confusing DFA and NFA requirements
2. ✗ Forgetting ε-transitions in NFA
3. ✗ Wrong pumping lemma string choice
4. ✗ Confusing decidable and recognizable
5. ✗ Thinking NP means “not polynomial”
6. ✗ Forgetting to show NP membership in NP-complete proofs
7. ✗ Confusing time and space complexity
8. ✗ Applying Rice’s theorem to syntactic properties

Study Checklist

Before Exam

• Review all definitions
• Memorize key theorems
• Practice automata design
• Master pumping lemma proofs
• Understand TM construction
• Know undecidability proofs
• Understand complexity classes
• Practice reductions
• Review closure properties
• Solve practice problems

Summary

This tutorial covered:

• Unit 1: Finite automata, regular languages, pumping lemma
• Unit 2: Context-free grammars, PDAs, CFL pumping lemma
• Unit 3: Turing machines, decidability, complexity theory
• Practice: Comprehensive problem sets
• Exam prep: Tips, common mistakes, quick reference

Key to success: Practice, practice, practice!

Good luck with your Theory of Computation exam! 🎓