Teoría de Autómatas y Lenguajes Formales

Jerarquía de Chomsky

Chomsky clasificó las gramáticas en cuatro familias, que difieren unas de otras en la forma que pueden tener sus reglas de producción.

Tipo 3 (Gramáticas regulares):

Pueden ser 2 tipos:

• Lineales por la derecha. A-> bC A->b A->lambda.
• Lineales por la izquierda. A->Cb A->b A->lambda.

Los lenguajes generados por estas gramáticas se llaman LENGUAJES REGULARES.

Tipo 2 (Gramáticas libres del contexto):

A->a

Los lenguajes generados por este tipo de gramáticas se llaman LENGUAJES LIBRES DEL CONTEXTO.

Tipo 1 (Gramáticas sensibles al contexto)

aAb-> ayb

Los lenguajes generados por las gramáticas tipo 1 se llaman LENGUAJES SENSIBLES AL CONTEXTO.

Tipo 0 (Gramáticas con estructura de frase)

Son gramáticas más generales, que por ello también se llaman gramáticas sin restricciones. Las producciones pueden ser de cualquier tipo permitido.

Autómata finito

Un autómata finito es una estructura matemática que representa un sistema o máquina abstracta.

La cinta de entrada (se extiende infinitamente hacia la derecha), está dividida en celdas, cada una de las cuales es capaz de almacenar un solo símbolo de un cierto alfabeto. La máquina es capaz de leer los símbolos de esta cinta de izquierda a derecha por medio de un cabezal de lectura. Cada vez que se lee un símbolo, el cabezal de lectura se mueve a la siguiente celta a la derecha y la máquina efectuará un cambio de estado o transición. esta transición está determinada por el mecanismo de control (Contiene un número finito de estados), programado para conocer cuál debe ser el nuevo estado, que dependerá de la combinación del estado actual y el símbolo de entrada leido.

Los autómatas finitos pueden considerarse como mecanismos aceptadores o reconocedores de palabras.

Autómata Finito Determinista (AFD)

Un autómata finito determinista se extiende como una quíntupla M=(Q,V,delta, q0, F), donde:

• Q: Conjunto finito de estados.
• V: Alfabeto de entrada.
• q0: Estado inicial.
• F intersección Q: Conjunto de estados finales.
• Delta: Q x V -> Q: Es la funcion de transicion.

Determinista: El nombre “Determinista” viene de la forma en que está definida la función de transición: Si en un instante t la máquina está en el estado q y lee el símbolo a entonces, en el instante siguiente t+1 la máquina cambia de estado y sabemos con seguridad cual es el estado al que cambia, que es precisamente delta(q,a).

Ejecución de un AFD:

1. -Se lee el símbolo actual, que es el apuntado por el cabezal de lectura. Si el cabezal apunta a una celda vacía entonces el AFD termina su ejecución, aceptando la palabra en caso de que el estado actual sea final y rechazando la palabra en caso contrario. Esto ocurre cuando se ha leído toda la palabra de entrada, y se produce una situación similar a tener una condición “fin de fichero” en la ejecución de un programa.
2. -Se calcula el estado siguiente a partir del estado actual y del símbolo actual según la función de transición, esto es, delta(Estado actual, símbolo actual)=Estado siguiente.
3. -El cabezal de lectura se mueve a una celda a la derecha.
4. -El estado siguiente pasa a ser el estado actual y vuelve al paso 1.

Autómata Finito No Determinista (AFND)

Un autómata finito no determinista es una quíntupla M=(Q,V,DELTA,q0,F) donde todos los componentes son como los AFDs, excepto la función de transición que se define ahora como: DELTA: QxV->P(Q). donde P(Q) denota el conjunto de las partes de Q (o conjunto de potencia 2^Q).

No determinista: El hecho de que el condominio de la funcion de transicion sea P(Q) es lo que añade esta característica de “No determinismo”: A partir del estado actual y del símbolo actual de entrada no se puede determinar de forma exacta cuál será el estado siguiente.

Autómata Finito con Lambda transiciones (AFND-LAMBDA)

Un autómata finito con Lambda-transiciones es básicamente un AFND al que se le permite cambiar de estado sin necesidad de consumir o leer un símbolo de entrada. Por eso la función de transición de un ANFD-Lambda se define: DELTA:Qx(V U {LAMBDA}) -> P(Q).

Configuración de un AF

La configuración de un autómata finito (Sin importar el tipo) en cierto instante viene dada por el estado del autómata en ese instante y por la porción de cadena de entrada que le queda por leer o procesar. La porción de cadena leída hasta llegar al estado actual no tiene influencia en el comportamiento futuro de la máquina. En este sentido podemos decir que un AF es una máquina sin memoria externa; son los estados los que resumen de alguna forma la información procesada. Algunos tipos de configuraciones:

• Configuración inicial: (q0, w), donde q0 es el estado inicial y w la palabra de entrada.
• Configuración de parada: Cualquier configuración en la que el autómata puede parar su ejecución, bien porque se haya procesado toda la entrada o bien porque se haya llegado a una situación donde no es aplicable ninguna transición.
• Configuración de aceptación: (qF, lambda) donde qF es un estado final del autómata. Una vez alcanzada esta configuración el autómata puede aceptar la palabra.

Lenguaje aceptado por M

Una palabra será aceptada por el autómata M, si partiendo de la configuración inicial w en la cinta de entrada, el autómata es capaz de alcanzar una configuración de aceptación.

Equivalencia entre AF

Decimos que dos autómatas finitos son equivalentes si y sólo si aceptan el mismo lenguaje. Veremos ahora que, en contra de lo que parece, los autómatas no deterministas (Con o sin lambda-transiciones) son igual de potentes que los autómatas finitos deterministas, en el sentido de que son capaces de reconocer los mismos lenguajes: Los lenguajes regulares.

Relación de aceptación de lenguajes entre un AFND y un AFD

Un lenguaje es aceptado por un AFND si y sólo si es aceptado por un AFD.

Relación de aceptación de lenguajes entre un AFND-LAMBDA y un AFND

Un lenguaje es aceptado por un AFND-Lambda si y sólo si es aceptado por un AFND.

Estados equivalentes

: Decimos que dos estados p y q de un AFD son equivalentes y lo notamos p~~q, si ambos estados apuntan al mismo estado con los mismos símbolos.

Autómata cociente: Dado un AFD M=(Q,V,delta,q0, F) se define el AUTÓMATA COCIENTE de M como M~~= (Q’,V,delta’,q’0,F’) donde:
Q’= Q/~~
delta’([q],a)=[delta(q,a)]
q’0=[q0]
F’=F/~~ 

Analizador léxico: El analizador léxico tiene como función generar una lista ordenada de tokens a partir de los caracteres de entrada. Estos tokens, o componentes léxicos, son usados por el analizador sintáctico para construir el correspondiente árbol sintáctico. Por otro lado, guarda información sobre algunos tokens, necesaria en el proceso de análisis y síntesis, en otra forma de atributos de esos componentes léxicos.
El analizador lexico lee caracteres de entrada hasta que detecta que con el último carácter leído se puede formar un token, o un error en su caso, comunica el evento correspondiente al analizador sintáctico. Si no hubo error, el AS procesa el token, y el AL no vuelve a entrar en juego hasta que el analizador sintáctico vuelva a necesitar otro token del flujo de entrada.
Otra de las funciones principales del AL es la detección y reparación de errores léxicos. Un error se produce cuando el AL detectar cualquier símbolo que es incapaz de reconocer y/o clasificar.

Analizador léxico: El analizador léxico tiene como función generar una lista ordenada de tokens a partir de los caracteres de entrada. Estos tokens, o componentes léxicos, son usados por el analizador sintáctico para construir el correspondiente árbol sintáctico. Por otro lado, guarda información sobre algunos tokens, necesaria en el proceso de análisis y síntesis, en otra forma de atributos de esos componentes léxicos.
El analizador lexico lee caracteres de entrada hasta que detecta que con el último carácter leído se puede formar un token, o un error en su caso, comunica el evento correspondiente al analizador sintáctico. Si no hubo error, el AS procesa el token, y el AL no vuelve a entrar en juego hasta que el analizador sintáctico vuelva a necesitar otro token del flujo de entrada.
Otra de las funciones principales del AL es la detección y reparación de errores léxicos. Un error se produce cuando el AL detectar cualquier símbolo que es incapaz de reconocer y/o clasificar.