Autômato de Pilha

Este programa cria um autômato de pilha a partir de um arquivo de configuração e verifica se um conjunto de cadeias são reconhecidas pelo autômato ou não. Essa resposta é dada em um arquivo de saída, informando quais foram as transições efetuadas.

O programa foi desenvolvido utilizando a linguagem Java e foi feito na forma de uma aplicação, sendo necessário rodá-lo em linha de comando. É possível fazer o download a seguir.

Trabalho desenvolvido em 2001 para a disciplina de Linguagens Formais e Autômatos. A utilização desse programa deve ser feita apenas para fins didáticos.

Autores

• Fábio Levy Siqueira

Software

Download: pda.jar

Manual

Para utilizar o programa, é necessário ter instalado o JDK. No prompt de comando deve-se executar:

java -jar pda.jar <entrada> <saida> <cadeias>

Onde os parâmetros significam:

<entrada>

Arquivo de entrada do autômato, que deve estar no seguinte formato:

# <comentários>
nome = <nome do autômato>
s = <estado inicial>
sigma = <simbolo1>, <simbolo2>, <simbolo3>, <...>
f = <estado final 1>, <estado final 2>, <...>
q = <estado1>, <estado2>, <...>
delta = <eo 1>, <sc 1>, <sd 1>, <ed 1>, <se 1>,
<eo 2>, <sc 2>, <sd 2>, <ed 2>, <se 2>,
<...>

Observações:

• No delta (relação de transição), o significado dos símbolos é o seguinte:
  • eo – Estado de origem
  • sc – Símbolo da entrada a ser consumido (” “, caso nenhum)
  • sd – Símbolo da pilha a ser desempilhado (” “, caso nenhum)
  • ed – Estado destino
  • se – Símbolos da pilha a ser empilhado
• os comentários podem acontecer em qualquer local do arquivo;
• o nome não pode conter vírgulas;
• o estado inicial deve ser único e definido em q;
• o alfabeto (sigma) deve conter apenas símbolos com tamanho (número de caracteres) iguais a 1, devendo ser únicos;
• o alfabeto da pilha (tau) deve conter apenas símbolos com tamanho (número de caracteres) iguais a 1, devendo ser únicos (mas podem ser iguais aos do alfabeto de entrada);
• o estado final deve estar definido em q;
• o conjunto de estados (q) deve conter estados cujos nomes não devem conter vírgulas e devem ser únicos;

A ordem não é importante para esses elementos, e caso deseje-se pular linha, é necessário apenas acrescentar o caracter “” para que seja reconhecido o pular de linha.

<saída>

O arquivo que se quer gravar o resultado das cadeias de entrada neste autômato de pilha, criando a árvore de computação e dizendo se reconheceu ou não. O formato é o seguinte:

Automato de Pilha : <nome do autômato de pilha>

Entrada : <cadeia processada> (<resultado: reconheceu ou não>)
(<estado>, <cadeia ainda a ser processada>, <conteúdo da pilha>) -> (<...>) -> ... -> (<...>) (<reconheceu: sim ou não>)

Entrada : <outra cadeia processada> (<resultado: reconheceu ou não>)
...

Observação: o <reconheceu: sim ou não> está na mesma linha que a árvore de computação, ou seja:
(<…>) -> (<…>) -> … -> (<…>) (<reconheceu: sim ou não>)

<cadeias>

Define quais cadeias serão processadas pelo autômato. O arquivo deverá estar no seguinte formato:

cadeia= <cadeia 1>, <cadeia 2>, <...>Observação: As cadeias podem estar em linhas diferentes, contanto que ao pular uma linha se coloque um “”. Ex:
Cadeia = <cadeia 1>,
<cadeia 2>,
<...>


Documentação

• Diagrama de classes
• Javadoc
• Exemplo: entrada / cadeias