6.045J/18.400J: Automata, Computability, and Complexity Handout ?? Profs. Shafi Goldwasser and Silvio Micali Due: Friday, March 22 Marc Horowitz Problem Set 6′, Bronwyn Eliot, Thursday 1pm

Problem 1: Limiting the Number of States

Generate a Turing machine as follows:

Take the desired regular expression and generate the equivalent DFA. Now, number all of its states. Call the set of numbers K_{DFA}. Set Σ_{TM} = Σ_{DFA} × (K_{DFA} ∪ #) × (K_{DFA} ∪ #). The first part of the symbol is a symbol from the RE’s alphabet. The second part is an optional state number, and the third part is an optional temporary number.

The Turing machine operates as follows. Rather than giving a rigorous table of δ values, I am listing each step in English. Each step is either directly translatable to a single TM operation involving a single state, or has been shown to be doable in a finite number of states.

1. Move left to the first character of the input string.

2. Set the state number to the number of s_{DFA}, goto state 3.

3. ⟨DFA symbol,DFA state,empty temporary⟩ translates to ⟨DFA symbol,DFA state,DFA next state⟩. If the input string is empty, go to state 5.

4. Copy temporary number to the next tape position’s state number. This can be done as follows.

(a) If the last digit of the temporary is 0, remove the zero and go to state 4b. If the last digit is 1, remove the one and go to state 4d. If there are no more digits, we are done. Move right and go to state 3.

(b) Move to the right, go to state 4c.

(c) Append a zero to the state number and go to state 4f.

(d) Move to the right, go to state 4e.

(e) Append a one to the state number and go to state 4f.

(f) Move to the left, and go to state 4a.

5. If the current state number is a final state, then accept the input. Otherwise, reject it.

This algorithm yields a Turing machine with about k = 10 states. More may be needed depending what is done with an accepting or rejecting state. But this is a general algorithm, which requires the same number of states, regardless of the complexity of the regular expression.