Tabela de transição de estado - State-transition table

Na teoria dos autômatos e na lógica sequencial , uma tabela de transição de estado é uma tabela que mostra para qual estado (ou estados, no caso de um autômato finito não determinístico ) uma máquina de estados finitos se moverá, com base no estado atual e outras entradas. É essencialmente uma tabela verdade em que as entradas incluem o estado atual junto com outras entradas e as saídas incluem o próximo estado junto com outras saídas.

Uma tabela de transição de estado é uma das muitas maneiras de especificar uma máquina de estado finito. Outras maneiras incluem um diagrama de estado .

Formas comuns

Unidimensional

As tabelas de transição de estado às vezes são tabelas unidimensionais, também chamadas de tabelas de características . Eles são muito mais como tabelas de verdade do que sua forma bidimensional. A dimensão única indica entradas, estados atuais, próximos estados e (opcionalmente) saídas associadas às transições de estado.

Tabela de transição de
estado (S: estado, I: entrada, O: saída)
Entrada Estado atual Próximo estado Resultado
Eu 1 S 1 S i O x
I 2 S 1 S j O y
Eu n S 1 S k O z
Eu 1 S 2 S i ′ O x ′
I 2 S 2 S j ′ O y '
Eu n S 2 S k ′ O z ′
Eu 1 S m S i ″ O x ″
I 2 S m S j ″ O y ″
Eu n S m S k ″ O z ″

Bidimensional

As tabelas de transição de estado são geralmente tabelas bidimensionais. Existem duas maneiras comuns de organizá-los.

Na primeira forma, uma das dimensões indica os estados atuais, enquanto a outra indica as entradas. As interseções de linha / coluna indicam os próximos estados e (opcionalmente) as saídas associadas às transições de estado.

Tabela de transição de
estado (S: estado, I: entrada, O: saída)
Entrada
Estado atual
Eu 1 I 2 Eu n
S 1 S i / O x S j / O y S k / O z
S 2 S i ′ / O x ′ S j ′ / O y ′ S k ′ / O z ′
S m S i ″ / O x ″ S j ″ / O z ″ S k ″ / O z ″

Na segunda forma, uma das dimensões indica os estados atuais, enquanto a outra indica os próximos estados. As interseções de linha / coluna indicam entradas e (opcionalmente) saídas associadas às transições de estado.

Tabela de transição de
estado (S: estado, I: entrada, O: saída, -: ilegal)
Próximo estado
Estado atual
S 1 S 2 S m
S 1 I i / O x - -
S 2 - - I j / O y
S m - I k / O z -

Outras formas

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

No outro extremo, tabelas separadas foram usadas para cada uma das transições dentro de uma única máquina de estado finito: "Tabelas E / OU" são semelhantes às tabelas de decisão incompletas em que a decisão para as regras que estão presentes é implicitamente a ativação de a transição associada.

Exemplo

Um exemplo de uma tabela de transição de estado junto com o diagrama de estado correspondente para uma máquina de estado finito é dado abaixo:

Tabela de transição de estado
Entrada
Estado atual
0 1
S 1 S 2 S 1
S 2 S 1 S 2
Diagrama de estado
Diagrama de estado FSM

Na tabela de transição de estado, todas as entradas possíveis para a máquina de estado finito são enumeradas nas colunas da tabela, enquanto todos os estados possíveis são enumerados nas linhas. Se a máquina estiver no estado S 1 (a primeira linha) e receber uma entrada de 1 (segunda coluna), a máquina permanecerá no estado S 1 . Agora, se a máquina estiver no estado S 1 e receber uma entrada de 0 (primeira coluna), a máquina fará a transição para o estado S 2 .
No diagrama de estado, o primeiro é denotado pela seta em loop de S 1 a S 1 marcada com 1, e o último é denotado pela seta de S 1 a S 2 marcada com 0. Este processo pode ser descrito estatisticamente usando Cadeias de Markov .

Para uma máquina de estado finito não determinística , uma entrada pode fazer com que a máquina esteja em mais de um estado, daí seu não determinismo . Isso é denotado em uma tabela de transição de estado pelo conjunto de todos os estados de destino incluídos em um par de chaves {}. Um exemplo de uma tabela de transição de estado junto com o diagrama de estado correspondente para uma máquina de estado finito não determinística é dado abaixo:

Tabela de transição de estado
Entrada
Estado atual
0 1
S 1 S 2 S 1
S 2 {S 1 , S 2 } S 2
Diagrama de estado
Diagrama de estado NFSM

Se a máquina estiver no estado S 2 e receber uma entrada 0, a máquina estará em dois estados ao mesmo tempo, os estados S 1 e S 2 .

Transformações de / para diagrama de estado

É possível desenhar um diagrama de estado de uma tabela de transição de estado. Uma sequência de etapas fáceis de seguir é fornecida abaixo:

  1. Desenhe os círculos para representar os estados fornecidos.
  2. Para cada um dos estados, percorra a linha correspondente e desenhe uma seta para o (s) estado (ões) de destino. Pode haver várias setas para um caractere de entrada se a máquina de estado finito for não determinística.
  3. Designe um estado como o estado inicial . O estado inicial é fornecido na definição formal de uma máquina de estados finitos.
  4. Designe um ou mais estados como estado de aceitação . Isso também é dado na definição formal de uma máquina de estados finitos.

Veja também

Referências

Leitura adicional

  • Michael Sipser: Introdução à Teoria da Computação . PWS Publishing Co., Boston 1997 ISBN  0-534-94728-X