Una de las aplicaciones mas importantes de las maquinas de estado finito es el reconocimiento de lenguajes (vital para el diseño y construcción de compiladores). Entre las máquinas de estado finito diseñadas especialmente para el reconocimiento de lenguajes, están los autómatas de estado finito (m´ aquinas de estado finito sin salida).
Definición. Un autómata de estado finito M = A, B, E, f, g } es una máquina de estado finito en el que los símbolos de salida son 0 y 1, es decir B = {0, 1}, además el estado actual determina la última salida.
Los estados, para los cuales la última salida es 1 se llaman estados de aceptación.
Ejemplo
Muestre que la máquina de estado finito cuyas tablas de transición de estados y de salida se dan en las siguientes tablas, es un autómata de estado finito.
f
|
g
| |||||
a
|
b
|
a
|
b
| |||
e0
|
e1
|
e0
|
e0
|
1
|
0
| |
e1
|
e2
|
e0
|
e1
|
1
|
0
| |
e2
|
e3
|
e0
|
e2
|
1
|
0
| |
Solución.
La gráfica de la máquina es la siguiente:
De la gráfica se observa que la salida es B = {0, 1}.
Además, según la gráfica se presenta la siguiente situación:
- Si se esta en e0, la última salida fué 0.
- Si estamos en los estados e2 o e3, la última salida fué 1.
Por tanto, es un autómata de estado finito.
Por lo general, en los autómatas de estado finito, los estados de aceptación se dibujan con círculos dobles y se omiten los símbolos de salida así:
No hay comentarios:
Publicar un comentario