Simulador de Autômatos com Pilha (PDA)

Este projeto consiste em um simulador de Autômatos com Pilha (Pushdown Automata) desenvolvido para a disciplina de Teoria da Computação (2025/1). O programa é capaz de ler a descrição técnica de um PDA e determinar se uma sequência de palavras é aceita ou rejeitada pela máquina.

---

Descrição do Problema

O objetivo acadêmico é implementar uma ferramenta que processe PDAs não-determinísticos (NPDA) definidos formalmente por:

• Estados ($Q$): Um conjunto finito de estados ${q_0, q_1, ..., q_{Q-1}}$.
• Alfabeto de Entrada ($\Sigma$): Letras minúsculas (a-z).
• Alfabeto da Pilha ($\Gamma$): Letras maiúsculas (A-Z), com 'Z' como símbolo inicial.
• Transições: Definidas pelo formato (estado_atual, letra, desempilha, empilha, proximo_estado).
• Símbolo Vazio: Representado pelo caractere & (epsilon).

---

Implementação Técnica

Para lidar com o não-determinismo intrínseco aos PDAs, o software utiliza um algoritmo de Busca em Largura (BFS).

Estruturas de Dados

• Pilha (Stack): Implementada para gerenciar os símbolos da memória auxiliar do autômato.
• Fila (Queue): Utilizada para gerenciar as "Configurações" (estado atual, posição na palavra e cópia da pilha) durante a exploração de todos os caminhos possíveis da BFS.
• Configuração: Cada nó da busca mantém sua própria instância da pilha, permitindo que o programa explore bifurcações causadas por transições vazias ou múltiplas opções de transição para o mesmo símbolo.

Gerenciamento de Memória

O código utiliza alocação dinâmica (malloc) para os estados, transições e para os nós da fila de processamento, garantindo que a memória seja liberada adequadamente após a simulação de cada palavra.

---

Formato de Entrada e Saída

Entrada

O programa espera os dados via stdin na seguinte ordem:

1. Dois inteiros: Q (número de estados) e T (número de transições).
2. T linhas descrevendo as transições: i c T X j.
3. Inteiro F (número de estados finais) e a lista dos IDs dos estados finais.
4. Sequência de palavras (uma por linha), terminando com *.

Saída

Para cada palavra, o programa imprime:

• palavra: sim (se aceita).
• palavra: nao (se rejeitada).

---

Compilação e Execução

O projeto foi desenvolvido em conformidade com os padrões da linguagem C.

Comando para Compilação:

gcc T1v3.c -o simulador_pda -Wall

Comando para Execução:

./simulador_pda < exemplo_entrada.txt

---

Requisitos de Desempenho

De acordo com as restrições do projeto, o simulador é capaz de processar máquinas de até 100 estados e 100 transições, com palavras de até 100 caracteres, garantindo resposta em tempo inferior a 1 minuto.