Exemplos de diagramas NFA.
Uma ferramenta, quatro pedidos. Todos os diagramas abaixo foram gerados de verdade.
O que é um diagrama NFA.
Um diagrama NFA é um diagrama de estados de um autômato finito não determinístico. Os círculos são estados, as setas são transições, uma seta que chega de fora indica o estado inicial e um círculo duplo indica um estado de aceitação.
Diferentemente de um DFA, um NFA pode fazer mais de uma transição com o mesmo símbolo de entrada e pode usar transições epsilon que não consomem entrada. Uma string é aceita quando pelo menos um caminho possível termina em um estado de aceitação.
- Standard
- OMG UML 2.5.1 §14 + Harel (1987) statechart
- Engine
- schematex-state
- Editable
- Double-click text, drag nodes
- Export
- SVG · PNG · PDF
Quem usa diagramas NFA.
Exercícios de linguagens regulares que mostram como uma máquina reconhece um sufixo, prefixo ou substring.
Pequenas construções de epsilon-NFA que tornam visível a união de uma expressão regular nas anotações de aula.
Prefixos alternativos de tokens desenhados como ramificações antes de serem convertidos em uma implementação.
Como criar um diagrama NFA em três etapas.
Descreva
Um parágrafo basta para começar.
Veja o diagrama
Gerado pelo mecanismo adequado.
Diga o que mudar
Cada edição fica salva como uma versão.
Dúvidas comuns
O que é um NFA?
Um autômato finito não determinístico é uma máquina de estados finitos que pode ter várias transições possíveis para um símbolo de entrada. Ele aceita quando pelo menos um caminho pela máquina termina em um estado de aceitação.
Qual é a diferença entre um NFA e um DFA?
Um DFA tem um único próximo estado para cada estado e símbolo de entrada. Um NFA pode ramificar para vários estados e pode incluir transições epsilon, mas NFAs e DFAs reconhecem a mesma classe de linguagens regulares.
O que é uma transição epsilon?
Uma transição epsilon muda de estado sem consumir um caractere da entrada. Ela é usada com frequência para unir ou dividir ramificações ao construir um NFA a partir de uma expressão regular.
Como os estados de aceitação são mostrados?
Um estado de aceitação, ou estado final, é mostrado com um círculo duplo. A máquina aceita somente se algum caminho terminar nesse estado depois que toda a entrada for lida.
Posso criar um NFA a partir de uma expressão regular?
Sim. Descreva a expressão e seu alfabeto e informe qualquer agrupamento ou alternância que você queira deixar explícito no diagrama de estados.
Outros diagramas para o mesmo trabalho.
Crie seu primeiro NFA agora.
Conta gratuita, sem cartão. Descreva a linguagem e veja o diagrama de estados em menos de um minuto.
Abrir o editor