Máquinas de estados finitos – semáforos, DFA, NFA e linguagens regulares
ComputaçãoAlgoritmos e resolução de problemasIdades 15–16
Carregando…
Entre para usarExecute passo a passo máquinas de estados de exemplo (semáforo, máquina de venda automática, catraca) com uma sequência de eventos e observe o estado atual, a saída e uma tabela de rastreio; adicione, arraste e conecte estados para desenhar sua própria máquina. O modo Aceitador testa quais palavras um DFA ou um NFA aceita (números binários divisíveis por 3, palavras terminadas em ab), com a tabela de transição de estados, uma expressão regular e uma gramática regular equivalentes e a conversão de NFA em DFA. Uma nota compara cada modelo com o sistema real para discutir abstração.
Aula: Máquinas de estados finitos: estados, transições e saídas; autômatos finitos determinísticos e não determinísticos; expressões regulares e gramáticas regulares
O que mostra
Uma máquina de estados finitos tem um conjunto finito de estados, um estado inicial, um alfabeto de entrada e transições da forma estado + símbolo → próximo estado. Ela não guarda nada além do estado atual. Uma máquina de Mealy produz saídas nas transições, uma máquina de Moore associa as saídas aos estados e um aceitador responde sim ou não: uma palavra pertence a uma linguagem? As linguagens aceitas por autômatos finitos são exatamente as linguagens regulares, também descritas por expressões regulares e gramáticas regulares. Todo NFA (autômato finito não determinístico) pode ser transformado em um DFA equivalente pela construção de subconjuntos.
Como usar
No modo Máquina com saída, escolha uma Máquina de exemplo e clique em Passo ou Executar para alimentar a máquina com os símbolos da fita, um de cada vez; os botões de símbolo enviam eventos extras. No modo Aceitador, escolha um Autômato de exemplo, digite uma Palavra a ler e percorra-a passo a passo; depois use Testar ou Listar palavras aceitas. Abra Editar máquina para adicionar, arrastar e conectar estados, ou clique em Converter NFA em DFA.
Parâmetros que você pode mudar
- Modo Máquina com saída, Aceitador
- Máquina de exemplo (modo Máquina com saída) Semáforo, Máquina de venda automática, Catraca
- Autômato de exemplo (modo Aceitador) DFA: números binários divisíveis por 3, NFA: palavras terminadas em ab, DFA: palavras terminadas em ab, DFA: número par de 1s (bit de paridade)
- Palavra a ler (vazia = palavra de exemplo)
- Velocidade de execução 0,5–4 símbolos/s
- Abrir o painel Editar máquina
Perguntas para explorar
- Quais detalhes de um semáforo real ficam de fora do modelo, e por que isso é aceitável?
- Acompanhando estado por estado, a palavra 110 é aceita pelo autômato de divisibilidade por 3?
- Por que o NFA para palavras terminadas em ab precisa de menos transições que o DFA equivalente?
