TechCodeview

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++

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:

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.