Theory of Computation

Answer:

Deterministic Finite Automaton (DFA):

• For each state and input symbol, exactly one transition
• No ε-transitions allowed
• Easier to implement in hardware/software
• δ: Q × Σ → Q

Non-Deterministic Finite Automaton (NFA):

• For each state and input symbol, zero or more transitions
• ε-transitions allowed
• More intuitive for design
• δ: Q × Σ_ε → P(Q)

Example: Language L = {strings over {0,1} containing "01"}

NFA: 3 states with ε-transition. DFA: Requires subset construction.

Proof by Contradiction:

1. Assume L is regular with pumping length p ≥ 1
2. Choose string s = 0ᵖ1ᵖ ∈ L with |s| = 2p ≥ p
3. By pumping lemma: s = xyz where |xy| ≤ p, |y| > 0, xy^i z ∈ L for all i ≥ 0
4. Since |xy| ≤ p: Both x and y consist only of 0s
5. Let |y| = k > 0: y = 0^k
6. Pumping with i = 0: xz = 0^{p-k}1^p
7. Since k > 0: p-k < p, so string has fewer 0s than 1s
8. Therefore: xz ∉ L, contradicting pumping lemma
9. Conclusion: L is not regular ∎

Step-by-step Construction:

1. Break down: (0+1)*01 = (0+1)* · 0 · 1
2. Construct NFA for (0+1)*:
   • State q₀ with self-loops on 0 and 1
   • q₀ is both start and final state
3. Construct NFA for 01:
   • q₁ →0→ q₂ →1→ q₃
   • q₃ is final state
4. Combine using concatenation:
   • Add ε-transition from final of (0+1)* to start of 01
   • Remove final status from (0+1)* part

Final NFA: States {q₀, q₁, q₂}, transitions preserve the pattern recognition for strings ending in 01.

Analysis: Union of two languages - L₁ (i=j) and L₂ (j=k)

Grammar G:

S → S₁ | S₂

S₁ → AB          // For i = j
A → aAb | ε      // Equal a's and b's
B → cB | ε       // Any number of c's

S₂ → CB          // For j = k  
C → aC | ε       // Any number of a's
B → bBc | ε      // Equal b's and c's
                        

Example derivations:

• aabbc (i=j=2, k=1): S → S₁ → AB → aAbB → aabB → aabbcB → aabbc
• abbcc (i=1, j=k=2): S → S₂ → CB → aCB → aB → abBc → abbBcc → abbcc

Step 1: Original grammar generates {aⁿbⁿ | n ≥ 1}

Step 2: Eliminate productions with mixed terminals/variables

S → ASB | AB
A → a
B → b
                        

Step 3: Break down productions with >2 variables

S → AC | AB    // where C → SB
A → a
B → b
C → SB
                        

Final CNF:

S → AC | AB
A → a
B → b
C → SB
                        

Input: 1ˣ (x ones)

Output: 1²ˣ (2x ones)

Algorithm:

1. For each 1 in input, write two 1s in output area
2. Mark processed 1s to avoid reprocessing
3. Use tape efficiently with markers

Detailed Steps:

1. Mark first 1 as X, move right to find blank
2. Write 11 after blank, return to next unmarked 1
3. Repeat until all 1s processed
4. Clean up: replace X's with blanks, position result
5. Accept

Transitions:
δ(q₀, 1) = (q₁, X, R)      // Mark and move right
δ(q₁, 1) = (q₁, 1, R)      // Skip over 1s
δ(q₁, B) = (q₂, 1, R)      // Write first copy
δ(q₂, B) = (q₃, 1, L)      // Write second copy
... (return transitions)
                        

Theorem: A_TM = {⟨M,w⟩ | M is TM that accepts w} is undecidable.

Proof by Contradiction:

1. Assume TM H decides A_TM
2. H behavior:
   • H(⟨M,w⟩) = accept if M accepts w
   • H(⟨M,w⟩) = reject if M rejects w or loops
3. Construct TM D:

   D on input ⟨M⟩:
   1. Run H on ⟨M,⟨M⟩⟩
   2. If H accepts: REJECT
   3. If H rejects: ACCEPT
                                   

4. Consider D(⟨D⟩):
   • If D accepts ⟨D⟩ → H rejects ⟨D,⟨D⟩⟩ → D rejects ⟨D⟩ ⚡
   • If D rejects ⟨D⟩ → H accepts ⟨D,⟨D⟩⟩ → D accepts ⟨D⟩ ⚡
5. Contradiction! Therefore H cannot exist.
6. Conclusion: A_TM is undecidable ∎

Step 1: Show VERTEX-COVER ∈ NP

• Certificate: Set S of vertices
• Verifier: Check |S| ≤ k and every edge has endpoint in S
• Time: O(|E|) - polynomial

Step 2: Reduce 3SAT ≤_p VERTEX-COVER

Given: 3SAT formula φ with variables x₁,...,xₙ and clauses C₁,...,Cₘ

Construct graph G:

1. Variable gadget: For each variable xᵢ, add edge (xᵢ, x̄ᵢ)
2. Clause gadget: For each clause Cⱼ = (ℓ₁ ∨ ℓ₂ ∨ ℓ₃), add triangle with vertices ℓ₁, ℓ₂, ℓ₃
3. Connect: Add edges from each literal to its negation in variable gadgets

Set k = n + 2m

Correctness:

• φ satisfiable ⟹ G has vertex cover of size k: Choose one literal per variable (satisfied one), two vertices per clause triangle not satisfied by chosen literals
• G has vertex cover of size k ⟹ φ satisfiable: Must choose exactly one literal per variable, assignment satisfies all clauses

Class Definitions:

• P: Languages decidable in polynomial time on deterministic TM
• NP: Languages decidable in polynomial time on non-deterministic TM (or verifiable in polynomial time)
• PSPACE: Languages decidable using polynomial space

Known Relationships:

Justification:

• P ⊆ NP: Deterministic TM is special case of non-deterministic TM
• NP ⊆ PSPACE: Can simulate NTM by exploring all computation paths using polynomial space
• PSPACE = NPSPACE: Savitch's theorem

Open Questions:

• P ?= NP: Most famous open problem
• NP ?= PSPACE: Also open
• Known: P ≠ EXPTIME (by time hierarchy theorem)

Practical Implications:

• If P = NP: Cryptography breaks down, optimization becomes easy
• Most experts believe P ≠ NP

Cook-Levin Theorem (1971): SAT (Boolean Satisfiability) is NP-complete.

Significance:

1. First NP-complete problem: Established the concept of NP-completeness
2. Reduction template: Other problems proven NP-complete by reducing SAT to them
3. Theoretical foundation: Launched complexity theory as major field

Proof Idea:

1. SAT ∈ NP: Easy - guess assignment, verify in polynomial time
2. Every L ∈ NP reduces to SAT:
   • For any L ∈ NP with verifier V
   • Given input x, construct formula φ
   • φ satisfiable ⟺ ∃ certificate c such that V accepts ⟨x,c⟩
   • φ encodes computation of V on ⟨x,c⟩

Construction Details:

• Variables for each cell of V's configuration at each time step
• Clauses ensure valid initial configuration
• Clauses ensure valid transitions
• Clauses ensure accepting final configuration

Impact: Led to discovery of thousands of NP-complete problems across all areas of computer science.