Theory of Computation: Automata, Grammars, and Turing Machines

(a) Alphabet, String, and Language Definitions

• Alphabet (Σ): A finite, non-empty set of symbols. Example: Σ = {0, 1} or Σ = {a, b}.
• String: A finite sequence of symbols chosen from an alphabet. Example: 0110, abba.
• Language (L): A set of strings over an alphabet Σ. Example: L = {a, ab, aab, aaab, ...} = a⁺b over Σ = {a, b}. ε denotes the empty string (length 0).

(b) DFA vs. NFA

• DFA: For each state and input symbol, exactly one next state is defined. No ε-transitions are allowed.
• NFA: For each state and input symbol, zero, one, or more next states are possible. ε-transitions are allowed.
• Power: Both accept the same class of languages (Regular Languages). Every NFA can be converted to an equivalent DFA.
• Design: DFA usually has more states; NFA design is generally easier.

(c) Regular Expression for Strings Ending in 101

R = (0 + 1)* 101

Explanation: (0+1)* generates any prefix, while 101 fixes the required ending.

(d) ε-Closure in Finite Automata

The ε-closure of a state q is the set of all states reachable from q using only ε-transitions (including q itself). This is essential for converting an NFA-with-ε to a DFA.

(e) Language Generated by CFG

For productions S → SS | ab | ba | ε, the language L(G) = { (ab + ba)* }. This represents the set of all strings over {a, b} that can be partitioned into blocks of 'ab' and 'ba'.

(f) The Chomsky Hierarchy

• Type-0 (Unrestricted): Recognized by Turing Machines.
• Type-1 (Context-Sensitive): Recognized by Linear Bounded Automata (LBA).
• Type-2 (Context-Free): Recognized by Pushdown Automata (PDA).
• Type-3 (Regular): Recognized by Finite Automata (FA).

Inclusion: Type-3 ⊂ Type-2 ⊂ Type-1 ⊂ Type-0.

(g) Universal Turing Machine (UTM)

A UTM is a Turing machine that simulates any other Turing machine M on an input w. It demonstrates that a single machine can be programmed to perform any computation, forming the theoretical foundation of modern stored-program computers.