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.
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.
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.
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:
Entrada
Estado atual
|
0 | 1 |
---|---|---|
S 1 | S 2 | S 1 |
S 2 | S 1 | S 2 |
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:
Entrada
Estado atual
|
0 | 1 |
---|---|---|
S 1 | S 2 | S 1 |
S 2 | {S 1 , S 2 } | S 2 |
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:
- Desenhe os círculos para representar os estados fornecidos.
- 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.
- Designe um estado como o estado inicial . O estado inicial é fornecido na definição formal de uma máquina de estados finitos.
- 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
- Lista de adjacências
- Matriz de adjacência
- Mesa de excitação
- Máquina de estados finitos
- Máquina moore
- Maquina de farelo
Referências
Leitura adicional
- Michael Sipser: Introdução à Teoria da Computação . PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X