Tabela de transição de estados para autômatos finitos

Na teoria dos autômatos, uma tabela de transição de estados é uma tabela que mostra para qual estado (ou estados, no caso de um autômato finito não-determinístico) a máquina de estados finitos irá se mover, com base no estado atual e em outras entradas. Uma tabela de estados é, essencialmente, uma tabela verdade em que algumas das entradas são o estado corrente, e as saídas incluem o estado seguinte, juntamente com outras saídas.

A tabela de estado é uma das muitas maneiras de especificar o comportamento de uma máquina de estado.

Formas comunsEditar

Tabelas de estado unidimensionaisEditar

Tabelas de estado unidimensionais se assemelham mais com as tabelas verdade do que as versões bidimensionais. As entradas são geralmente colocados no lado esquerdo, e separadas das saídas, que estão à direita. As saídas vão representar o próximo estado da máquina. Aqui está um exemplo simples de uma máquina de estado com dois estados e duas entradas:

A B Estado Atual Próximo Estado Saída
0 0 S1 S2 1
0 0 S2 S1 0
0 1 S1 S2 0
0 1 S2 S2 1
1 0 S1 S1 1
1 0 S2 S1 1
1 1 S1 S1 1
1 1 S2 S2 0

S1 e S2 poderiam ser representados como bits 0 e 1.

Tabelas de estados bidimensionaisEditar

Tabelas de transição de estado são tipicamente tabelas bidimensionais. Existem duas formas comuns para organizá-las.

  • A dimensão vertical (ou horizontal) indica estados atuais, a dimensão horizontal (ou vertical) indica eventos, e as células (interseções de linha/coluna) na tabela indicam o próximo estado se ocorrer um evento (e, possivelmente, a ação associada a este estado de transição).
Tabela de transição de estados
  Eventos
Estado
E1 E2   ...   En
S1 - Ay/Sj ... -
S2 - - ... Ax/Si
... ... ... ... ...
Sm Az/Sk - ... -

(S: estado, E: evento, A: ação, -: transição ilegal)


  • A dimensão vertical (ou horizontal) indica estados atuais, a dimensão horizontal (ou vertical) indica próximos estados, e as interseções de linha/coluna contém o evento que irá levar a um próximo estado particular.
Tabela de transição de estados
      próximo
atual
S1 S2   ...   Sm
S1 - - ... Ax/Ei
S2 Ay/Ej - ... -
... ... ... ... ...
Sm - Az/Ek ... -

(S: estado, E: evento, A: ação, -: transição impossível)

Outras formasEditar

Transições simultâneas em várias máquinas de estados finitos podem ser mostradas no que é efetivamente uma tabela de transição de estado n-dimensional, em que pares de linhas mapeiam estados atuais para os próximos estados. Esta é uma alternativa para representar a comunicação entre máquinas de estados interdependentes.

ExemploEditar

Um exemplo de uma tabela de transição de estado para um autômato M em conjunto com o diagrama de estado correspondente é dado abaixo.

Tabela de Transição de Estados
  Entrada
Estado
1 0
S1 S1 S2
S2 S2 S1
  Diagrama de Estados
 

Todas as possíveis entradas para a máquina são enumeradas entre as colunas da tabela. Todos os estados possíveis são enumerados nas linhas. A partir da tabela de transição de estado dada acima, é fácil ver que, se a máquina está em S1 (primeira linha), e a próxima entrada é um caractere 1, a máquina vai ficar em S1. Se um caractere 0 chega, a máquina fará a transição para S2, como pode ser visto a partir da segunda coluna. No diagrama isso é denotado pela seta a partir de S1 para S2, marcada com um 0.

Para um autômato finito não-determinístico (AFN), uma nova entrada pode levar a máquina para mais de um estado, por isso ele é não-determinístico. Isto é indicado em uma tabela de transição de estado por um par de chaves {} com o conjunto de todos os próximos estados entre eles. Um exemplo é dado abaixo.

Tabela de Transição de Estados para um AFN
  Entrada
Estado
1 0 ε
S1 S1 { S2, S3 } Φ
S2 S2 S1 Φ
S3 S2 S1 S1

Aqui, se uma máquina não determinística no estado S1 lê uma entrada 0, poderá ir para dois estados ao mesmo tempo, os estados S2 e S3. A última coluna define se existe uma transição vazia (ε) entre os estados. Esse caractere especial (ε) permite que o AFN vá para um estado diferente sem que seja fornecida nenhuma entrada. No estado S3, o AFN pode mover-se para S1 sem consumir nenhum caractere de entrada. Os dois casos acima fazem o autômato finito ser descrito como não-determinístico.

Transformações de/para diagrama de estadoEditar

É possível traçar um diagrama de estado a partir de uma tabela. Uma seqüência de passos é dada abaixo:

  1. Desenhe círculos para representar os estados dados.
  2. Para cada um dos estados, examine a linha correspondente e desenhe uma seta para o estado de destino. Pode haver várias flechas para um dado caractere de entrada se o autômato for um AFN.
  3. Designar um estado como o estado inicial. O estado inicial é dado na definição formal do autômato.
  4. Designar um ou mais estados de aceitação. Isto também é dado na definição formal.

Leituras complementaresEditar

  • Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X