TODO: do jeito que está atualmente, só aceita AFD.
Sumário:
Segundo Sipser [1], um automâto finito determinístico é dado por uma quíntupla
- Q é um set finito de estados
-
$\Sigma$ é um set finito de símbolos (alfabeto) -
$\delta: Q \times \Sigma \rightarrow Q$ é a função de transição (que relaciona estados utilizando os símbolos) -
$q_0 \in Q$ é o estado inicial -
$F \subseteq Q$ é o set de estados aceitáveis (finais)
Resumidamente, isso implica que todo AFD deverá "consumir" o símbolo durante a transição, de forma que, caso não o faça, será inválido.
Note que, de acordo com a definição, somente é possível existir um único símbolo de entrada
Usando a definição do livro:
A nondeterministic finite automaton is a 5-tuple
$(Q,\Sigma, \delta, q_0, F)$ where:
- Q is a finite set of states,
$\Sigma$ is a finite alphabet,$\delta: Q\times \Sigma_\epsilon \rightarrow P(Q)$ is the transition function,$q_0\in Q$ is the starte state, and$F \subseteq Q$ is the set of accept states.-- Sipser [1]
Novamente, isto implica em dizer que haverá apenas um único estado inicial.
Note que poderá existir uma transição
Uma outra característica do AFN, é que ele pode ter a mesma aída (arestas) para dois, ou mais, nós distintos.
Exemplo retirado da internet
Um arquivo de entrada deverá ser formatado como o código abaixo. Isso implica em dizer, que deverá haver espaços separando símbolos/estados.
s0 ; s2 s0 a > s0 s0 b > s1 s1 a > s1 s1 b > s2 s2 a > s2 s2 b > s2 wrd : aabb
Lambda será representado por /
- O programa deve elaborar o AFD e AFN equivalente a esta entrada e então, analisar a palavra, também definida no arquivo.
- O simulador vai executar passo a passo, i.e, uma transição por vez
- Antes de passar ao próximo passo, o simulador poderá gerar um arquivo dot com base no estado atual.
- A ferramenta deverá ser por linha de comando, onde irá aceitar um arquivo como parâmetro.
O arquivo dot gerado irá conter todo o grafo, alterando apenas a cor (posição) do estado atual, e a seta indicando o próximo estado, ou seja, ele deverá analisar 1 posição à frente.
- Como rodar algum programa:
# executando um arquivo de exemplo sobre a pasta inputs ...
# ... dentro da pasta afdn_animator (pasta com os códigos), digite
./target/release/afdn_animator ./inputs/default.txt
# em seguida, gere as imagens com base nos arquivos dots, dentro da pasta ...
# ... o jeito mais rápido é digitar
./to_file
# por fim, caso seja necessário (ou vá rodar outro teste), remova os arquivos antigos
./clear_outputsNote que a build atual foi feita no LINUX e PARA O LINUX, portanto, caso use windows, será necessário realizar a build de produção novamente
Note também que, os scripts foram feitos para o bash, dessa forma, caso utilize-os no windows ou terá que ser feita uma adaptação para arquivos .bat ou utilizar o WSL2
- Outros comandos úteis:
# dev build
cargo build
# Production build
cargo build --release
# limpa a pasta dot/
./clear_outputs
# gera uma imagem para cada arquivo dot dentro da pasta dot/ e, em seguida, gera o gif de todas as imagens
./to_file# Para gerar um arquivo JPEG:
dot −Tjpeg fonte.dot -o saida.jpg
# Para gerar um gif de todas as imagens geradas
convert -delay 60 -loop 0 *.jpg output.gif
# Para instalar:
sudo apt install build-essential imagemagick graphviz-
Exemplo de um arquivo dot gerado
digraph G { rankdir=LR; overlap="scale"; sep="0.1"; pad="1"; nodesep="0.5"; ranksep="1"; node [style="rounded,filled"] s0 [color="#467050", fontcolor="white"] s2 [peripheries=2] start [label= "", shape=none,height=.0,width=.0] start -> s0 s0 -> s1 [label="b"] s0 -> s0 [label="a", color="#ad2a2a"] s1 -> s1 [label="a"] s1 -> s2 [label="b"] s2 -> s2 [label="a"] s2 -> s2 [label="b"] }
- Introduction to the theory of computation. Michael Sipser. 2ª ed. 2005. MIT. Thomsom. ISBN 0-534-95097-3.