Implementação de um AFD (Autômato Finito Determinístico)

Trabalho da disciplina de Linguagens Formais e Autômatos (LFA).

É uma aplicação de linha de comando escrita em TypeScript e executada com o runtime Bun. Ela permite criar, salvar, carregar, excluir e testar Autômatos Finitos Determinísticos.

1. O que é um AFD

Um Autômato Finito Determinístico é definido formalmente por uma 5-upla:

M = (Q, Σ, δ, q₀, F)

Símbolo	Significado	No código
Q	Conjunto finito de estados	states: Set<string>
Σ	Alfabeto (conjunto finito de símbolos)	alphabet: Set<string>
δ	Função de transição δ: Q × Σ → Q	transitions: Record<estado, Record<símbolo, estado>>
q₀	Estado inicial (q₀ ∈ Q)	initialState: string
F	Conjunto de estados finais (F ⊆ Q)	finalStates: Set<string>

Determinístico significa que, para cada par (estado, símbolo), existe no máximo uma transição. O autômato lê a cadeia símbolo a símbolo, mudando de estado conforme δ, e aceita a cadeia se terminar a leitura em um estado final.

2. Modelagem utilizada

Os tipos estão em src/types.ts:

• AfdParams: o AFD na forma de execução. Usa Set para Q, Σ e F, já que consultas de pertinência com has() são O(1).
• SavedAfd: o AFD na forma serializável para o JSON. Usa arrays, porque Set não é representável em JSON.
• NamedAfdParams: um AfdParams com name, usado nos menus.

A conversão entre as duas formas é feita por toRuntime() (arrays para Sets) e toSaved() (Sets para arrays) em src/index.ts, evitando casts incorretos.

A função de transição é um dicionário aninhado:

transitions["q0"]["a"] = "q1"   // δ(q0, a) = q1

Se uma combinação (estado, símbolo) não existe no dicionário, não há transição definida e a cadeia é rejeitada.

3. Como executar

Pré-requisito: Bun instalado.

bun install      # instala dependências de desenvolvimento
bun src/index.ts # inicia a aplicação

Ao iniciar, aparece o menu:

[1] - Nova AFD
[2] - Carregar AFD
[3] - Excluir AFD
[4] - Testar cadeia
s - Sair

Fluxo típico da demonstração:

1. [2] Carregar AFD e escolher uma das AFDs já salvas em data.json.
2. [4] Testar cadeia, digitar a cadeia e ver o passo a passo da execução.

Vale lembrar que o teste só fica disponível depois de criar ou carregar um AFD.

4. Núcleo do algoritmo

A função testAFDString(str, afd) em src/index.ts implementa a simulação:

1. estadoAtual ← estadoInicial
2. Se a cadeia é vazia (ε):
       aceita se estadoInicial ∈ F, senão rejeita
3. Para cada símbolo c da cadeia:
       a. se c ∉ Σ              → REJEITA (símbolo inválido)
       b. próximo ← δ(estadoAtual, c)
       c. se próximo não existe → REJEITA (sem transição)
       d. estadoAtual ← próximo
4. Ao fim: aceita se estadoAtual ∈ F, senão rejeita

Antes de processar a cadeia, o programa imprime a definição completa do autômato (alfabeto, estados, estado inicial, estados finais e todas as transições). A cada passo ele imprime uma linha no formato No estado X, leu "c" e foi para Y, marcando quando Y é um estado final. Isso deixa a execução visível durante a apresentação.

5. Critérios da rubrica

Critério	Onde é atendido
Define Q, Σ, q₀, F, δ	types.ts e o builder em startAFDBuilder()
Função de transição determinística	dicionário aninhado, um único destino por (estado, símbolo)
Processa cadeias aceitas e rejeitadas	testAFDString()
Trata cadeia vazia (ε)	bloco explícito if (str.length === 0)
Trata símbolos inválidos	checagem alphabet.has(symbol)
Trata configurações incorretas	validações no builder: alfabeto vazio, conjunto de estados vazio, estado inicial fora de Q, estado final fora de Q e destino de transição fora de Q
Permite configurar vários AFDs	criação, persistência e seleção via menu
Modularidade e ausência de duplicação	leitura e escrita do JSON centralizadas em readSavedAFDs e writeSavedAFDs

O builder pede uma transição para cada par (estado, símbolo), então todo AFD criado pela aplicação tem função de transição total. Os AFDs já gravados em data.json podem ter transições parciais, e nesse caso a ausência de transição leva à rejeição da cadeia.

6. AFDs de exemplo

O arquivo data.json acompanha alguns AFDs prontos. Os três abaixo são os usados na demonstração; os demais (teste2, teste3, quarta1, quarta2) vieram de testes feitos durante o desenvolvimento.

qtd-par-de-a (aceita vazia)

Aceita cadeias com quantidade par de a, ignorando os b. Serve para demonstrar o tratamento da cadeia vazia, já que zero a é par e o estado inicial par também é final.

• Σ = {a, b}, Q = {par, impar}, q₀ = par, F = {par}
• δ(par,a)=impar, δ(par,b)=par, δ(impar,a)=par, δ(impar,b)=impar

Cadeia	Resultado	Motivo
`` (ε)	ACEITA	zero a é par e o estado inicial é final
aa	ACEITA	dois a
abba	ACEITA	dois a
a	REJEITA	um a, para em impar
x	REJEITA	símbolo x ∉ Σ

termina-em-b

Aceita cadeias sobre {a, b} que terminam com b.

Cadeia	Resultado
b, ab, aab, abab	ACEITA
a, ba, `` (ε)	REJEITA

abc-sequencia

Aceita cadeias que começam com a sequência abc e continuam apenas com c.

Cadeia	Resultado	Motivo
abc, abcc	ACEITA	terminam em q3
ab	REJEITA	para em q2, que não é final
abca	REJEITA	não existe δ(q3, a)
xyz	REJEITA	x ∉ Σ

7. Roteiro sugerido de apresentação

1. Conceito: explicar a 5-upla (Q, Σ, δ, q₀, F) e o que é determinismo.
2. Modelagem: mostrar types.ts e como cada parte da 5-upla vira código.
3. Execução: carregar qtd-par-de-a e testar nesta ordem:
   • cadeia vazia (Enter sem texto), que é aceita;
   • aa, aceita;
   • a, rejeitada por parar em estado não final;
   • x, rejeitada por símbolo inválido.
4. Interpretação: ler em voz alta o passo a passo impresso (estado, símbolo lido, próximo estado).

8. Estrutura do projeto

.
├── src/
│   ├── index.ts   # menu, persistência e simulação do AFD
│   └── types.ts   # definição dos tipos (a 5-upla)
├── data.json      # AFDs salvos
├── docs/          # enunciado e rubrica do trabalho
├── package.json
└── README.md