Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Problem 1

Draw the machine and input encoded below using the encoding scheme from class.
Encoding Turing machines:
Let {a0,a1,a2,...} be the set of all symbols (excluding   ) that may appear on a TM tape.
Let {q0,q1,q2,...} be the set of all states (excluding h) that may be part of a TM.
Symbols, states and tape-head moves get encoded by the encoding function e as follows:
SymbolsStatesMoves
e(□) = 0
e(ai) = 0i+2 		e(h) = 0
e(qi) = 0i+2 		e(S) = 0
e(L) = 00
e(R) = 000
The transition t := δ(p,x) = (q,y,m) gets encoded as: e(t) = e(p)1e(x)1e(q)1e(y)1e(m)1.
The machine T with start state q and transitions t1,t2,..., tk gets encoded as: e(T) = e(q)1e(t1)1e(t2)1...1e(tk)1.
Input z := ai1 ai2 ... ain gets encoded as e(z) = 11e(ai1)1e(ai2)1 ... e(ain)1.
Machine T and input z get encoded as e(T)e(z). 


00010001001001001011000100010010100011001001001000100011001000100100100011001010101011110010001001

Problem 2

Simulate the machine on the input (from the above). Specifically: does the machine halt or not? and if the machine halts, what configuration does it halt in?
Congrats. You are now a Universal Turing Machine!

Problem 3: CFG Review

Write a context-free grammar for the language $\{a^n b^m a^n | m,n \geq 0\}$.