Page 60 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS
P. 60
60
Se debe entender que para esta máquina Δ (P,X) = Q o sea que la máquina solo pasará al
estado Q si estando en el estado P lee X de la cinta. Por consiguiente, un diagrama de
transición para un AFD no es más que una representación gráfica de la función de
transición de la máquina.
Se deduce entonces que: el autómata (Q, ∑, Δ, , F), acepta la cadena no vacía de
0
, ,… sí y solo sí existe una serie de estados ,…. todos pertenecientes a F,
2
1
1
0,
que cumplen con la función de transición ᵟ( −1 , ).
El autómata finito y el principio de determinismo implican 2 aseveraciones:
1- Que de cada estado solo debe salir un arco que sale para cada símbolo del alfabeto. De lo
contrario estando en un estado en donde hay más de un arco para un mismo símbolo no se
sabría cuál elegir. Si este fuera el caso no hay determinismo.
2- El diagrama del autómata debe estar completamente definido. Es decir, debe existir por
lo menos un arco para cada símbolo del alfabeto. Si no es así puede llegarse a un estado
que leyendo un símbolo que no posee arco, no podría realizar ninguna función de
transición. En consecuencia, no es determinista.
Lo que define y establece los conceptos anteriores es que:
- Δ es una función, que debe retornar un producto o resultado.
- El dominio de Δ, es Q X ∑
Se dice que un diagrama de transición es determinista si cumple con estas definiciones.
Ejemplo 1:
LETRA LETRA
3 3
1
DIGITO DIGITO
2
No está completamente definido, porque el estado 2 es un estado donde no se puede aplicar
ninguna transición, sea que se reciba letra o digito, no hay nada definido o determinado. Entonces
técnicamente no es completamente definido; y por consiguiente no es determinista; sin embargo,
puede ajustarse para cumplir con los requisitos del determinismo, pero hacerlo o no, no cambia
el hecho de que llegan a las mismas conclusiones y el diagrama se ve menos saturado. Ahora bien,
si cae en el estado y se da cualquiera de las 2 entradas definidas, sin duda hay que establecer que
es un error.
Si se implementa este AFD en una máquina, solo habría que invocar un error.
