Autómatas Deterministas

Existen dos grandes grupos de autómatas, los autómatas deterministas y los no deterministas. Aunque antes de hablar de éstos, hay que definir lo que es un autómata finito, también llamado máquina de estado finito, que es una máquina computacional que realiza operaciones con una entrada para intentar proporcionar una salida. Esta salida dependerá de las transacciones que se producen entre los diferentes estados según se va analizando la entrada.

Un autómata finito determinista, es por tanto un autómata finito, que además tiene la restricción de que, partiendo de un estado, éste únicamente puede tener una transacción a otro estado utilizando un símbolo concreto. Existen procesos de minimización para conseguir transformar un autómata no determinista en determinista, ya que todos los AFND(Autómatas finitos no deterministas) tiene un AFD(Autómatas finitos deterministas) asociado. Esta operación de minimización simplifica el autómata y produce un automáta que al ser el resultado de la minimización, es más eficiente que el anterior.

AF Deterministas, AFD’s: se definen mediante una quíntupla ( E, Q, f, q0, F), donde:

- E: alfabeto de entrada.
- Q: conjunto de estados, es conjunto finito no vacío, realmente un alfabeto para distinguir a los estados.
- f: Q x Q, función de transición.
- q0 Q, estado inicial.
- F Q: conjunto de estados finales o de aceptación.

AFD como reconocedor de un Lenguaje:

• Cuando un AF transita desde q0 a un estado final en varios movimientos, se ha producido el RECONOCIMIENTO o ACEPTACIÓN de la cadena de entrada.
• Cuando un AF no es capaz de alcanzar un estado final, se dice que el AF NO RECONOCE la cadena de entrada y que ésta NO PERTENECE al lenguaje reconocido por el AF.

Automata Finito Determinista

Lenguaje asociado a un AFD:

- Sea un AFD = (Σ, Q, f, q0, F), se dice que una palabra x es aceptada o reconocida por el AFD si f’(q0,x) F.
- Se llama lenguaje asociado a un AFD al conjunto de todas las palabras aceptadas por éste.

Es posible tener varios autómatas que reconozcan el mismo lenguaje. Para todo autómata que tiene otro con de la misma equivalencia (i.e. reconoce el mismo lenguaje) donde el número de estadosdel autómata sea el mínimo.

Se dispone de un descriptor del lenguaje (lenguaje regular): gramática tipo 3, AFD, AFND, expresión regular. Se plantean problemas de decisión:

• ¿El lenguaje descrito es vacío?
• ¿Existe una determinada cadena w en el lenguaje descrito?
• ¿Dos descripciones de un lenguaje describen realmente el mismo lenguaje? Nota: usualmente los lenguajes son infinitos, con lo que no es posible plantear la pregunta y recorrer el conjunto INFINITO de cadenas.

Autómatas con la misma equivalencia

1.- Estados de automatas con la misma equivalencia  en AFD’s distintos:

- Sean 2 AFD’s: ( ,Q,f,q0,F) y ( ’,Q’,f’’q0’,F’)
- los estados p,q / p Q y q Q’ son de la misma equivalencia (pEq) si se verifica que f(p,x) F f”(q,x) F’ x E*
2.- Estados de equivalencia en AFD’s distintos:
- Dos AFD’s tienen equivalencia si reconocen el mismo lenguaje, es decir: Si f(q0,x) F f(q0’,x) F’ x E*.
- Dos AFD’s  tienen equivalencia  si lo son sus estados iniciales: q0 E q0

Lenguajes y Gramáticas

Uno de los principales temas sobre los que trata la teoría de autómatas son las gramáticas y los lenguajes formales.

Cuando se habla de una gramática nos referimos al conjunto de reglas con las que se puede generar todas las posibilidades combinatorias de ese lenguaje. Además existen dos tipos de lenguajes, naturales y formales. En teoría de autómatas, se estudian principalmente los lenguajes formales y su utilidad computacional, en los cuales se utilizan las reglas combinatorias de estilo matemático.

Es importante saber hasta dónde puede llegar un lenguaje. Un alfabeto será siempre finito, esto significa que es un conjunto de símbolos finito con el cual se forman palabras. Las palabras son también finitas, pero el lenguaje puede tener un número infinito de palabras.

Ahora pongamos por ejemplo un alfabeto formado por dos caracteres {a, b}. Podemos crear combinaciones como aab, aba, abba entre otras, pero si definimos un lenguaje en el que el número de símbolos "a" deba ser mayor que el número de símbolos "b", abba ya no sería una sentencia válida para ese lenguaje.

Otro aspecto importante de los lenguajes es la palabra vacía, denominada como λ, la cual representa una cadena de longitud 0.

En cuanto a las gramáticas, se las representa como (V, Σ, p, S), donde:

- V es un conjunto finito de símbolos no-terminales.
- Σ es el alfabeto ó conjunto de símbolos terminales.
- P es una relación en (V υ Σ)* son las reglas de producción tal que los primeros elementos en p contienen al menos un símbolo es V.
- S € V es el símbolo de comienzo.

Además existen 4 tipos de gramáticas, ordenados según la Jerarquía de Chomsky.

- Gramática tipo 0: sin restricciones. Generan todos los lenguajes capaces de ser reconocidos por una Máquina de Turing.
- Gramática tipo 1: gramáticas sensibles al contexto. Se reconocen por un autómata linealmente acotado.
- Gramática tipo 2: gramáticas libres del contexto. Reconocidos por autómatas a pila.
- Gramática tipo 3: gramáticas regulares. Son los lenguajes aceptados por los autómatas finitos.

Una gramática formal está en Forma normal de Chomsky (FNC) si todas sus reglas de producción son de alguna de las siguientes formas:

A→BCo
A→αo

donde A, B y C son símbolos no terminales (o variables) y α es un símbolo terminal.

También se puede dar como:

A→BCo
A→αo
S→ε

donde S es el símbolo distinguido (o inicial) de la gramática, A es un símbolo noterminal (o variable), B y C también son símbolos no terminales pero distintos de S , α es un símbolo terminal, y ε es la cadena nula (o vacía).

Como último apunte, se dice que una gramática independiente del contexto (GIC) está en Forma normal de Greibach (FNG) si todas y cada una de sus reglas de producción tienen un consecuente que empieza por un símbolo terminal.

Formalmente,cualquiera de las reglas tendrá la estructura:

A→aw

Donde "A" es el antecedente de la regla, que en el caso de las GIC debe ser necesariamente un solo smbolo auxiliar. Por su parte, "a" es el mencionado comienzo del consecuente y, por tanto, un símbolo terminal. Finalmente, "w" representa una concatenación genérica de elementos gramaticales, esto es, una sucesión exclusivamente de auxiliares, inclusive, pudiera ser la palabra vacía; en este caso particular, se tendría una regla llamada "terminal":

A→a

Existe un teorema que prueba que cualquier GIC, cuyo lenguaje no contiene la palabra vacía, si no lo está ya, se puede transformar en otra equivalente que sí esté en FNG.

Referencias:

Lenguajes y Gramáticas

Autómatas a Pila

Máquinas de Turing

La máquina de Turing fue ideada por Alan Turing como una herramienta para resolver la decibilidad de los problemas matemáticos. Fue el primer modelo formal de computador, y con él se demostró que hay problemas que no son resolubles mediante un ordenador.

Ésta, a priori, sencilla máquina, es capaz de realizar complejos cálculos tales como los realizables por un ordenador cualquiera.

En su implementación, la máquina de turing se sirve de una cinta infinita donde va leyendo y escribiendo caracteres usando un cabezal, transicionando a su vez por diversos estados del autómata asociado hasta llegar o no a un estado final.

Usos de la Máquina de Turing:

- Complejidad Computacional

El modelo se compone de dos alfabetos, uno de entrada y otro de salida, además de un carácter especial llamado blanco (b), un conjunto de estados finitos y otro de transiciones entre estados.

Se representa como (Q, Σ, s, b, F, Γ, ∂):

- Q es un conjunto finito de estados.
- Σ es un conjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto de máquina o de entrada.
- Γ es un estado finito de símbolos de cinta, denominado alfabeto de cinta (Σ ⊆ Γ).
- s pertenece Q es el estado inicial.
- b pertenece Γ es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
- F ⊆ Q es el conjunto de estados finales de aceptación.
- ∂ : Q x Γ → Q x Γ x {L, R} es una función parcial denominada función de transición, donde L es un movimiento a la izquierda y R es el movimiento a la derecha.

Existen en la literatura un abundante número de definiciones alternativas, pero todas ellas tienen el mismo poder computacional, por ejemplo se puede añadir el símbolo S como símbolo de "no movimiento" en un paso de cómputo.

Su funcionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres (la cinta, la cual puede ser infinita) pertenecientes al alfabeto de entrada. La máquina va leyendo una celda de la cinta en cada paso, borrando el símbolo en el que se encuentra posicionado su cabezal y escribiendo un nuevo símbolo perteneciente al alfabeto de salida, para luego desplazar el cabezal a la izquierda o a la derecha (solo una celda a la vez). Esto se repite según se indique en la función de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.