Implemente um simulador para maquina de turing deterministicas. O simulador devera apresentar
como saida, para uma maquina M e palavra de entrada w, a computação de M para w.

Uma configuração instantanea de M é um par [e, xay], em que:
• e ∈ E é o estado atual;
• x ∈ Γ ∗ é a palavra situada `a esquerda do cabeçote de leitura;
• a ∈ Γ é o sḿbolo sob o cabeçote; e
• y ∈ Γ ∗ é a palavra `a direita do cabeçote até o ultimo símbolo diferente de |__|;

Deve-se usar como base o algoritmo abaixo:


Entrada: (1) a MT, dado por i, F e D, e
(2) a palavra de entrada, dada por w
Saída: sim ou não


se w = λ então s ←|__| ;
se w = ay, para a ∈ Σ e y ∈ Σ ∗ então s ← a;
e ← i;
enquanto D[e, s] é definido faça


se δ(e, a) = [e' , b, D] então
[e, xacy] [e' , xbcy]; ou [e, xa] [e' , xb |__|]; para c ∈ Γ


senão se δ(e, a) = [e , b, E] então


[e, xcay] [e' , xcπ(by)]; para c ∈ Γ
fimse;
e ← e' ;
s ← c;
fimenquanto;
se e ∈ F então


retorne sim
senão
retorne não
fimse

Função π : Γ ∗ → Γ ∗ : π(w) elimina de w os brancos á direita
do último símbolo diferente de branco.
π(w) = λ se w ∈ { |__|} ∗
xa se w = xay, a ∈ Γ − {|__| } e y ∈ {|__| } ∗ .


A entrada do programa é um arquivo texto contendo uma MT representado da seguinte
forma:
0 1 2 ; //estados
a b ; //alfabeto de entrada
a b ; //alfabeto da fita
(0,a,a,D,1) , //(de 0, lendo a, escreve a, direita, vai p/ 1)
(1,b,b,E,2) ; //(de 1, lendo b, escreve b, esquerda, vai p/ 2)
0 ; //estado inicial
0 1 ; //estados finais