A tabela de transição é basicamente uma representação tabular da função de transição. São necessários dois argumentos (um estado e um símbolo) e retorna um estado (o 'próximo estado').
Uma tabela de transição é representada pelos seguintes itens:
- As colunas correspondem aos símbolos de entrada.
- As linhas correspondem aos estados.
- As entradas correspondem ao próximo estado.
- O estado inicial é indicado por uma seta sem fonte.
- O estado de aceitação é indicado por uma estrela.
Exemplo 1:
Solução:
A tabela de transição de determinado DFA é a seguinte:
java x c++
Estado atual | Próximo estado para entrada 0 | Próximo estado da entrada 1 |
---|---|---|
→q0 | q1 | q2 |
q1 | q0 | q2 |
*q2 | q2 | q2 |
Explicação:
- Na tabela acima, a primeira coluna indica todos os estados atuais. Nas colunas 0 e 1, os próximos estados são mostrados.
- A primeira linha da tabela de transição pode ser lida como, quando o estado atual é q0, na entrada 0 o próximo estado será q1 e na entrada 1 o próximo estado será q2.
- Na segunda linha, quando o estado atual é q1, na entrada 0, o próximo estado será q0, e na entrada 1 o próximo estado será q2.
- Na terceira linha, quando o estado atual é q2 na entrada 0, o próximo estado será q2, e na entrada 1 o próximo estado será q2.
- A seta marcada com q0 indica que é um estado inicial e o círculo marcado com q2 indica que é um estado final.
Exemplo 2:
Solução:
... em java
A tabela de transição de determinado NFA é a seguinte:
Estado atual | Próximo estado para entrada 0 | Próximo estado da entrada 1 |
---|---|---|
→q0 | q0 | q1 |
q1 | q1, q2 | q2 |
q2 | q1 | terceiro trimestre |
*q3 | q2 | q2 |
Explicação:
- A primeira linha da tabela de transição pode ser lida como, quando o estado atual é q0, na entrada 0 o próximo estado será q0 e na entrada 1 o próximo estado será q1.
- Na segunda linha, quando o estado atual é q1, na entrada 0 o próximo estado será q1 ou q2, e na entrada 1 o próximo estado será q2.
- Na terceira linha, quando o estado atual é q2 na entrada 0, o próximo estado será q1, e na entrada 1 o próximo estado será q3.
- Na quarta linha, quando o estado atual é q3 na entrada 0, o próximo estado será q2, e na entrada 1 o próximo estado será q2.