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

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde abril de 2013).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.

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[editar | editar código-fonte]

Tabelas de estado unidimensionais[editar | editar código-fonte]

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 bidimensionais[editar | editar código-fonte]

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 formas[editar | editar código-fonte]

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[editar | editar código-fonte]

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
DFAexample.svg

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 estado[editar | editar código-fonte]

É 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[editar | editar código-fonte]

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