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 comuns

Tabelas de estado unidimensionais

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:

S₁ e S₂ poderiam ser representados como bits 0 e 1.

Tabelas de estados bidimensionais

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).

(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.

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

Outras formas

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.

Exemplo

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 S₁ (primeira linha), e a próxima entrada é um caractere 1, a máquina vai ficar em S₁. Se um caractere 0 chega, a máquina fará a transição para S₂, como pode ser visto a partir da segunda coluna. No diagrama isso é denotado pela seta a partir de S₁ para S₂, 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.

Aqui, se uma máquina não determinística no estado S₁ lê uma entrada 0, poderá ir para dois estados ao mesmo tempo, os estados S₂ e S₃. 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 S₃, o AFN pode mover-se para S₁ 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 estado

É 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 complementares

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