Theory of Computation: Solved Questions on Automata

DFA vs NFA: Key Differences

Deterministic Finite Automata (DFA) vs Nondeterministic Finite Automata (NFA):

Deterministic Finite Automata (DFA)

• For each input symbol, only one transition is possible.
• No ε (epsilon) transitions are allowed.
• The transition function gives exactly one next state.
• Easier to implement in code.

Nondeterministic Finite Automata (NFA)

• For one input symbol, multiple transitions may be possible.
• ε-transitions may exist.
• The transition function gives zero, one, or many next states.
• Easier to design.

Pumping Lemma for Regular Languages

Statement

If L is a regular language, then there exists a pumping length p such that any string w in L with |w| ≥ p can be written as:

w = xyz

such that:

1. |xy| ≤ p
2. |y| > 0
3. xyⁿz ∈ L for all n ≥ 0

Primary Purpose

The Pumping Lemma is mainly used to:

• Prove that a language is not regular.
• Show the limitations of finite automata.

Algebraic Laws of Regular Expressions

Let R, S, and T be regular expressions.

1. Commutative Law

R + S = S + R

Example: a + b = b + a

2. Associative Law

For Union

(R + S) + T = R + (S + T)

For Concatenation

(RS)T = R(ST)

3. Distributive Law

Left Distributive

R(S + T) = RS + RT

Right Distributive

(R + S)T = RT + ST

4. Identity Law

R + ∅ = R

Rε = εR = R

5. Idempotent Law

R + R = R

6. Null Law

R∅ = ∅R = ∅

7. Absorption Law

R + RS = R(ε + S)

Chomsky Normal Form (CNF)

A Context-Free Grammar (CFG) is said to be in Chomsky Normal Form if every production is of the form:

1. A → BC
2. A → a

where A, B, and C are variables and a is a terminal.

Example

S → AB, A → a, B → b

Turing Machines vs Pushdown Automata

Turing Machine

A Turing Machine (TM) is an abstract computational model consisting of:

• An infinite tape
• A read/write head
• A set of states and transition functions

It can read, write, and move left or right on the tape.

Key Differences: TM vs PDA

Turing Machine (TM)

• Uses infinite tape memory.
• More powerful computational model.
• Accepts recursively enumerable languages.

Pushdown Automata (PDA)

• Uses stack memory (LIFO).
• Less powerful computational model.
• Accepts context-free languages.

Post's Correspondence Problem (PCP)

Definition

Given two lists of strings:

A = (x₁, x₂, ..., x_n)

B = (y₁, y₂, ..., y_n)

Find a sequence of indices i₁, i₂, ..., i_k such that:

x_i1x_i2...x_ik = y_i1y_i2...y_ik

Significance

• PCP is an undecidable problem.
• It is used to prove the undecidability of many other problems in the Theory of Computation.

Equivalence of NFA and DFA

Theorem Statement

For every NFA, there exists an equivalent DFA that accepts the same language.

Proof (Subset Construction Method)

Consider an NFA: N = (Q, Σ, δ, q₀, F)

Construct an equivalent DFA: D = (Q', Σ, δ', q₀', F') where:

1. Q' = Power set of Q
2. q₀' = {q₀}
3. δ' maps subsets of states
4. F' contains all subsets having at least one final state of the NFA

How It Works

• Each DFA state represents a set of NFA states.
• The DFA simulates all possible moves of the NFA simultaneously.
• Hence, both automata accept the exact same language.

Closure Properties of Regular Languages

Closure under Intersection

Let L₁ and L₂ be regular languages accepted by DFAs:

M₁ = (Q₁, Σ, δ₁, q₁, F₁) and M₂ = (Q₂, Σ, δ₂, q₂, F₂)

Construct a product DFA:

M = (Q₁ × Q₂, Σ, δ, (q₁, q₂), F₁ × F₂)

This DFA accepts strings accepted by both M₁ and M₂. Hence, regular languages are closed under intersection.

Closure under Reversal

If L is regular, then there exists an NFA/DFA accepting L. To obtain the reversal:

1. Reverse all transitions.
2. Make the final states the initial states.
3. Make the initial state the final state.

The resulting automaton accepts:

L^R = { w^R | w ∈ L }

Hence, regular languages are closed under reversal.

Applications of Turing Machines

Turing Machines have critical applications in several fields:

1. Compiler Design: Parsing and syntax analysis.
2. Language Processing: Defining formal grammars and languages.
3. Complexity Theory: Classifying problems into complexity classes (P vs NP).
4. Artificial Intelligence: Modeling cognitive processes and computability.

Pumping Lemma Definition

If L is regular, then there exists a pumping length p such that any string w with |w| ≥ p can be written as w = xyz, satisfying:

1. |xy| ≤ p
2. |y| > 0
3. xyⁱz ∈ L for all i ≥ 0

General Closure Properties

Regular languages are closed under the following operations:

1. Union
2. Intersection
3. Complementation
4. Concatenation
5. Kleene Star

Union

If L₁ and L₂ are regular, then L₁ ∪ L₂ is also regular.

Intersection

Product automata can be constructed to prove closure under intersection.

Complementation

Swap final and non-final states in the DFA.

Concatenation

Connect the final states of the first automaton to the start state of the second using ε-transitions.

Kleene Star

Add ε-transitions from the final states back to the initial state.

Hence, regular languages are closed under all the above operations.

Enumerable vs Recursively Enumerable Languages

Enumerable Language

A language is enumerable if there exists a machine (an enumerator) that can list all strings of the language.

Recursively Enumerable Language

A language is recursively enumerable if there exists a Turing Machine (TM) that accepts every string in the language.

Key Differences

Enumerable Languages

• Generates strings.
• Uses an enumerator.
• May list strings infinitely.

Recursively Enumerable Languages

• Recognizes strings.
• Uses a Turing Machine.
• The Turing Machine may not halt for rejected strings.

Relationship

Every recursive language is recursively enumerable, but the converse is not always true.

Undecidable Problems in Computation

Definition

A problem is undecidable if no algorithm or Turing Machine can always give a correct yes/no answer for every input instance.

The Halting Problem

Given a Turing Machine M and an input w, determine whether M halts on w. This problem is proven to be undecidable.

Important Undecidable Problems

1. Halting Problem
2. Post's Correspondence Problem (PCP)
3. Turing Machine Equivalence Problem
4. Ambiguity Problem for Context-Free Grammars (CFG)

Significance

Undecidability shows the fundamental limitations of computation, proving that some problems cannot be solved by computers regardless of time or memory.

Variants of Turing Machines

There are several alternative models of Turing Machines, all of which have equivalent computational power to a standard Turing Machine:

1. Multi-tape TM: Uses multiple tapes for computation.
2. Multi-track TM: A single tape divided into multiple tracks.
3. Non-deterministic TM: Has multiple possible moves from any given state.
4. Universal TM: Can simulate any other Turing Machine when given its description.
5. Two-dimensional TM: The tape extends in two dimensions (grid).
6. Linear Bounded Automata (LBA): A Turing Machine where the tape length is limited by the size of the input.