Page 59 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS
P. 59
59
MATRIZ
0 1
A B A
B C B
C B C
ÉXITO
El lenguaje de este autómata seria: todas las cadenas de 0 y 1 , donde pueden haber un uno, ningún
uno o varios unos y la cantidad de ceros que exista siempre es par. Esto es:
L (Σ= {0,1}) = {W ϵ ( , ) / la cantidad de ceros es par}
∗
Autómatas finitos:
Los autómatas finitos y los lenguajes regulares se encuentran en el nivel más bajo de la
clasificación dada. Para la mayoría de las aplicaciones que requieren técnicas de reconocimiento
de patrones. Ejemplo de esto, son los lenguajes de programación, por lo que es su mayor
aplicación y uso en la construcción de compiladores.
La presentación de una máquina que puede leer una cinta, una cabeza lectora que se desplaza,
etc., que estuvimos viendo, es solo una representación informal de la potencia de un autómata.
De hecho, se construyen máquinas con las mismas propiedades de computación, incorporando
diferentes tecnologías, que al final no son más que autómatas finitos deterministas.
Esquema del autómata finito:
CINTA DE ENTRADA
LA CABEZA SE MUEVE EN
ESTA DIRECCIÓN
CABEZA DE LECTURA
MECANISMO DE CONTROL (INDICADOR DE ESTADOS)
Un autómata finito (AFD) se define así:
Un AFD es una quíntupla (Q, ∑, Δ, , F)
Donde:
Q → Es un conjunto finito de estados.
∑ → Es el alfabeto de la máquina.
Δ → Es la función de transición equivalente a Q X ∑ ∊ Q.
F → Es un subconjunto de Q, que representan sólo los estados de
aceptación.
