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

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

Crie um programa que implemente um autômato de pilha descrito em arquivo. O arquivo terá o formato abaixo:

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

Os itens do alfabeto, da pilha e dos estados finais devem ser separados por espaço. O número de transições é um inteiro e cada transição deve estar na forma:

qi r pi qj po

• qi = estado atual
• r = caractere lido da entrada
• pi = item retirado da pilha
• qj = próximo estado
• po = item inserido na pilha

Exemplo de arquivo:

0 1
0 #
q3
5
q0 e e q1 #
q1 0 e q1 0
q1 1 0 q2 e
q2 1 0 q2 e
q2 e # q3 e

O exemplo acima implementa o autômato de pilha que reconhece a linguagem L = {0^n1^n | n > 1} (veja a imagem abaixo). Após ler o arquivo, o programa deverá solicitar uma string ao usuário. Em seguida, o programa deverá informar se a string é reconhecida ou não pelo autômato.