Taula de transició d'estats

En teoria d'autómates i llògica seqüencial, una taula de transició d'estats és una taula que mostra qué estat es mourà un autómata finito dau, basant-se en l'estat actual i atres entrades. Una taula d'estats és essencialment una taula de veres en la qual algunes de les entrades són l'estat actual, i les eixides inclouen el següent estat, junt en atres eixides.

Una taula d'estats és una de les moltes maneres d'especificar una màquina d'estats, atres formes són un diagrama d'estats, i una equació característica.

Quan es tracta d'un autómata finito no determinista, llavors la taula de transició mostra tots els estats que es mourà l'autómata.

Formes comunes

Taules d'estats d'una dimensió

També cridades taules característiques, les taules d'estats d'una dimensió són més com a taules de veres que com les versions de dos dimensions. Les entrades són normalment colocades a l'esquerra, i separades de les eixides, les quals estan a la dreta. Les eixides representaran el següent estat de la màquina. Ací hi ha un eixemple senzill d'una màquina d'estats en dos estats, i dos entrades combinacionales:

A	B	Estat Actual	Següent Estat	Eixida
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

S₁ i S₂ representarien provablement els bits individuals 0 i 1, ya que un simple bit solament té dos estats.

Taules d'Estats de dos dimensions

Les taules de transició d'estats són normalment taules de dos dimensions. Hi ha dos formes comunes per a construir-les.

• La dimensió vertical indica els Estats Actuals, la dimensió horisontal indica events, i les celes (interseccions fila/columna) de la taula contenen el següent estat si ocorre un event (i possiblement l'acció enllaçada a esta transició d'estats).

Taula de Transició d'Estats

Events State	I1	I2	...	In
S1	-	Ai/Sj	...	-
S2	-	-	...	Ax/Si
...	...	...	...	...
Sm	Az/Sk	-	...	-

(S: estat, I: event, A: acció, -: transició illegal)

• La dimensió vertical indica els Estats Actuals, la dimensió horisontal indica els següents estats, i les interseccions fila/columna contenen l'event el qual dirigirà al següent estat particular.

Taula de Transició d'Estats

next current	S1	S2	...	Sm
S1	Ai/Ij	-	...	-
S2	-	-	...	Ax/Ii
...	...	...	...	...
Sm	-	Az/Ik	...	-

(S: estat, I: event, A: acció, -: transició impossible)

Eixemple

Un eixemple d'una taula de transició d'estats per a una màquina M junt en el corresponent diagrama d'estats està donat avall.

Taula de Transició d'Estats   Entrada Estat 1 0 S1 S1 S2 S2 S2 S1

Diagrama d'estats DFAexample.svg

Totes les entrades possibles a la màquina estan enumerades a través de les columnes de la taula. Tots els estats possibles estan enumerats a través de les files. Des de la taula de transició d'estats anterior, és fàcil vore que si la màquina està en S₁ (la primera fila), i la següent entrada és el caràcter 1, la màquina permaneixerà en S₁. Si aplega un caràcter 0, la màquina realisarà la transició a S₂ com pot vore's des de la segona columna. En el diagrama açò és denotat per la flecha des de S₁ a S₂ etiquetada en un 0.

Per a un autómata finito no determinista (AFND), una nova entrada pot causar que la màquina estiga en més d'un estat, ya que és no determinista. Açò es denota en una taula de transició d'estats per un parell de claus { } en un conjunt de tots els estats objectiu entre ells. Es dona un eixemple avall.

Taula de Transició d'Estats per a un AFND

Entrada Estat	1	0	ε
S1	S1	{ S2, S3 }	Φ
S2	S2	S1	Φ
S3	S2	S1	S1

Ací, una màquina no determinista en l'estat S₁ llegint una entrada de 0 causarà que estiga en dos estats al mateix temps, els estats S₂ i S₃. L'última columna definix la transició llegal d'estats del caràcter especial, ε. Este caràcter especial permet als AFND moure's a un estat diferent quan no hi ha cap entrada. En l'estat S₃, el AFND pot moure's a S₁ sense consumir cap caràcter d'entrada. Els dos casos anteriors configuren a l'autómata finito no determinista.

Referències

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