4ª avaliação de Aspectos Teóricos da Computação

4ª avaliação da disciplina EXA858 – Aspectos Teóricos da Computação.
Valor: 10,0 na 3ª unidade.
Prazo: 15/05/2016, 23:59 (via e-mail).
Em dupla.

Crie um programa que implemente uma máquina de Turing descrita em arquivo. O arquivo terá o formato abaixo:

alfabeto
número de transições
transição1
transição2
...

Os itens do alfabeto devem ser separados por espaço. O estado inicial é o primeiro estado a aparecer na lista de transições. O número de transições é um inteiro e cada transição deve estar na forma:

qi,fi,qj,fo,M

• qi = estado atual
• fi = caractere lido da fita
• qj = próximo estado
• fo = caractere gravado na fita
• M = movimento da fita, que pode ser S (fique onde está), L (esquerda) ou R (direita)

Os ítens da transição estão separados por vírgula para facilitar a inserção de espaços em branco na fita, além de que a inserção de elementos na fita é opcional e pode ser omitita. O estado de aceitação deve se chamar sempre ‘qA’ e o de rejeição é ‘qR’. Exemplo de arquivo:

0
15
q0, ,qR,,R
q0,x,qR,,R
q0,0,q1, ,R
q1, ,qA,,R
q1,x,q1,,R
q1,0,q2,x,R
q2,x,q2,,R
q2,0,q3,,R
q2, ,q4,,L
q3, ,qR,,R
q3,x,q3,,R
q3,0,q2,x,R
q4,0,q4,,L
q4,x,q4,,L
q4, ,q1,,R

O exemplo acima implementa a máquina de Turing que decide A = {0^2^n | n >= 0} (veja a imagem abaixo). Após ler o arquivo, o programa deverá solicitar uma string ao usuário, essa string será a fita da máquina. Em seguida, o programa deverá informar se a string na fita é aceita ou rejeitada pela máquina.