# 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:
| A | B | Estado Atual | Próximo Estado | Saída |
| 0 | 0 | S$_1$ | S$_2$ | 1 |
| 0 | 0 | S$_2$ | S$_1$ | 0 |
| 0 | 1 | S$_1$ | S$_2$ | 0 |
| 0 | 1 | S$_2$ | S$_2$ | 1 |
| 1 | 0 | S$_1$ | S$_1$ | 1 |
| 1 | 0 | S$_2$ | S$_1$ | 1 |
| 1 | 1 | S$_1$ | S$_1$ | 1 |
| 1 | 1 | S$_2$ | S$_2$ | 0 |
S$_1$ e S$_2$ 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).
Tabela de transição de estados :
| Eventos Estado | E$_1$ | E$_2$ | ... | E$_n$ |
| S$_1$ | - | A$_y$/S$_j$ | ... | - |
| S$_2$ | - | - | ... | A$_x$/S$_i$ |
| S$_m$ | A$_z$/S$_k$ | - | ... | - |
(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 | S$_1$ | S$_2$ | ... | S$_m$ |
| S$_1$ | - | - | ... | A$_x$/E$_i$ |
| S$_2$ | A$_y$/E$_j$ | - | ... | - |
| S$_m$ | - | A$_z$/E$_k$ | ... | - |
(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 :
| Tabela de Transição de Estados  Entrada Estado 1 0 S$_1$ S$_1$ S$_2$ S$_2$ S$_2$ S$_1$ | 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$_1$ (primeira linha), e a próxima entrada é um caractere 1, a máquina vai ficar em S$_1$. Se um caractere 0 chega, a máquina fará a transição para S$_2$, como pode ser visto a partir da segunda coluna. No diagrama isso é denotado pela seta a partir de S$_1$ para S$_2$, 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 | ε |
| S$_1$ | S$_1$ | { S$_2$, S$_3$ } | Φ |
| S$_2$ | S$_2$ | S$_1$ | Φ |
| S$_3$ | S$_2$ | S$_1$ | S$_1$ |
Aqui, se uma máquina não determinística no estado S$_1$ lê uma entrada 0, poderá ir para dois estados ao mesmo tempo, os estados S$_2$ e S$_3$. 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$_3$, o AFN pode mover-se para S$_1$ 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:
* Desenhe círculos para representar os estados dados.
* 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.
* Designar um estado como o estado inicial. O estado inicial é dado na definição formal do autômato.
* 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