logo

Tabela de Transição

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:

Tabela de Transição

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:

Tabela de Transição

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.