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

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

3 thoughts on “Autômato de Pilha

  1. Boa noite Fábio, você postou o .jar de seu projeto achei muito interessante. Sou estudande de Ciência da Computação e gostaria muito de ver seu código para analisar e estuda-lo. Seria possivel enviar o projeto? Totalmente para fins acadêmicos, inclusive inclui-lo como referência de estudo.
    Obrigado desde já.

    1. Olá Thiago;

      Fico feliz pelo seu interesse. Porém, como o desenvolvimento de um autômato de pilha é um trabalho frequente em faculdades de computação, decidi – há muito tempo – não disponibilizar o código fonte deste programa. Sei que essa minha decisão atrapalha algumas pessoas que tem interesses meramente didáticos, mas ainda assim prefiro manter essa posição a fim de evitar plágios. Desculpe.

      Se você tem interesse em analisar o código de um autômato, recomendo fortemente você analisar a biblioteca AdapLib. Ela ainda não trata um autômato de pilha, mas de um ponto de vista teórico e didático ela apresenta alguns aspectos bastante interessantes.

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *