teoría autómatas

Introducción a la teoría de Autómatas 1

José M. Godoy Giménez

1. AUTOMATAS FINITOS Y LENGUAJES REGULARES.

1.1 Análisis léxico.Los diagramas de transiciones se pueden emplear como herramienta de diseño para producir rutinas de

análisis léxico. No obstante, el código generado directamente a partir de un diagrama de transiciones no siemprerepresenta la mejor solución al problema; se obtiene una solución más elegante si se emplean tablas detransiciones. Una tabla de transición es un arreglo bidimensional cuyos elementos proporcionan el resumen de undiagrama de transiciones correspondiente.

1.2 Autómatas finitos deterministas.Un Autómata Finito Determinista consiste en un dispositivo que puede estar en cualquier estado entre un

número finito, uno de los cuales es el estado inicial y por lo menos uno es un estado de aceptación. A estedispositivo está unido un flujo de entrada por medio del cual llegan en secuencia los símbolos de un alfabetodeterminado. La máquina tiene capacidad para detectar los símbolos conforme llegan y, basándose en el estadoactual y el símbolo recibido, ejecutar una transición consistente en cambiar a otro estado o la permanencia en elmismo. El programa de un Autómata Finito Determinista no debe contener ambigüedades (para un estado undeterminado símbolo sólo puede producir una determinada acción).

Se dice que un Autómata Finito Determinista acepta su cadena de entrada si, después de comenzar suscálculos en el estado inicial la máquina cambia a un estado de aceptación después de leer el último símbolo de lacadena. Si después de leer el último símbolo no queda en estado de aceptación, se dice que la cadena ha sidorechazada. Si la entrada es una cadena vacía (λ) será aceptada si y sólo si el estado inicial es también un estado deaceptación. Un Autómata Finito Determinista consiste en una quíntupla ( S, Σ, δ, ι, F) donde:

a. S, es un conjunto finito de estados.b. Σ, es el alfabeto de la máquina.c. δ, es una función (función de transición) de S× Σ a S.d. ι, (un elemento de S) es el estado inicial.e. F (un subconjunto de S) es el conjunto de estados de aceptación.

La interpretación de la función de transición δ de un autómata finito determinista es que δ(p,x)=q sí y sólosí la máquina puede pasar de un estado p a un estado q al leer el símbolo x.

El diagrama de transición determinista sólo debe tener un arco que sale de un estado para cada símbolodel alfabeto. Además, dicho diagrama está completamente definido, es decir, debe existir un arco para cadasímbolo del alfabeto.

1.3 Límites de los autómatas finitos deterministas.

LENGUAJES REGULARESSe define Σ* como el conjunto de cadenas de longitud finita formadas por el alfabeto Σ. Un subconjunto

de Σ * se denomina lenguaje. Si M es un autómata finito determinista ( S, Σ, δ, ι, F), la colección de cadenas queacepta constituye un lenguaje con respecto al alfabeto Σ. Este leguaje se representa como L(M), que es el lenguajeque acepta el autómata M. Un lenguaje de la forma L(M) para un autómata finito M se denomina lenguaje regular.

TEOREMA 1.1.Para cualquier alfabeto S, existe un lenguaje que no es igual a L(M) para cualquierautómata finito determinista M.

Demostración.Puesto que cualquier arco de un autómata finito determinista que esté rotulado con un símbolo que no

pertenece a Σ no tendrá efecto alguno sobre el procesamiento de una cadena en Σ*, podemos considerar sólo lasmáquinas con alfabeto Σ. Sin embargo, la colección de autómatas finitos deterministas con alfabeto Σ es contableya que podemos elaborar de forma sistemática una lista de todas las máquinas posibles con un estado, seguidas portodas las máquinas con dos estados, luego las de tres estados, etc. Por otra parte, el número de lenguajes conrespecto al alfabeto Σ es incontable, ya que el conjunto infinito Σ* tiene un número incontable de subconjuntos. Porlo tanto hay más lenguajes que autómatas finitos deterministas, por lo que deben existir lenguajes que no sonaceptados por este tipo de máquinas.



LENGUAJES NO REGULARESTEOREMA 1.2Si un lenguaje regular contiene cadenas de la forma xnyn para enteros arbitrariamentegrandes, entonces debe contener cadenas de la forma xmyn, donde m y n no son iguales.

Demostración.Suponiendo que M es un autómata finito determinista tal que L(M) contiene xnyn para un n

arbitrariamente grande. Entonces, debe existir un entero positivo k mayor que el número de estados en M y tal quexkyk se encuentre en L(M). Puesto que existen más símbolos en xk que estados en M, el proceso de aceptación dexkyk dará como resultado que se recorra más de una vez alguno de los estados de M antes de llegar a alguna de las yde la cadena. Es decir, durante la lectura de algunas x se recorrerá una ruta circular del diagrama de transicionesde la máquina. Si j es el número de x leídas al recorrer esta ruta, entonces la máquina puede aceptar la cadenaxk+jyk recorriendo esta ruta una vez más. Por lo tanto, existe un entero positivo m (específicamente k+j) que no esigual a k, tal que xmyk se encuentra en L(M).

Una consecuencia inmediata de este teorema es que el lenguaje { xnyn: n ∈N} no es regular. Si unautómata finito determinista aceptase expresiones aritméticas que contienen paréntesis; debería aceptar, porejemplo, expresiones de la forma (n…)n para enteros n arbitrariamente grandes, sin embargo el teorema nos indicaque aceptaría por ejemplo expresiones cuyo número de paréntesis izquierdo difiera de el número de paréntesisderecho.

1.4 Autómatas finitos no deterministas.Considerando la restricción de determinismo, se puede llegar a otro tipo de máquinas conceptuales,

conocidas como autómatas finitos no deterministas. Se diferencian de los autómatas finitos deterministas en que latransición puede ser incierta, ya que es posible aplicar más de una transición, o ninguna, como sucede en unamáquina que no está completamente definida.

Un autómata finito no determinista que analiza una cadena puede lleva a un error porque se tomen lasdecisiones incorrectas en los puntos donde existen varias opciones. Por ello se dice que un autómata finito nodeterminista acepta una cadena si es posible que su análisis deje la máquina en un estado de aceptación.

Un autómata finito no determinista consiste en una quíntupla (S, Σ, ρ, ι, F) donde:S, es un conjunto finito de estados.Σ, es el alfabeto de la máquina.ρ, es un subconjunto de S×Σ×S.ι, es el estado inicial (elemento de S).F, (Subconjunto de S) conjunto de estados de aceptación.

En esta definición la tupla (p,x,q) está en δ sí y sólo sí el autómata puede pasar del estado p al estado q alleer el símbolo x de la cadena de entrada. (p,w,q1) y (p,w,q2) pueden estar en δ aunque q1#q2.

TEOREMA 1.3Para cada autómata finito no determinista, existe un autómata finito determinista queacepta exactamente el mismo lenguaje.

Demostración.Suponiendo que M es el autómata finito no determinista definido por (S, Σ, ρ, ι, F). Se debe demostrar que

existe un autómata finito determinista que acepta las mismas cadenas. Para ello se define otro autómata M’, con(S’,Σ’, δ’, ι’, F’), donde S’=P(S), ι’={ι}, F’ es la colección de subconjunto de S que contienen por lo menos unestado de F, y δ es la función de S’× Σ a S’ tal que para cada x en Σ y s’ en S’, δ (s’, x) es el conjunto de todo s enS tal que (u, x, s) está en ρ para algún u en s’ (es decir, δ(s’, x) es el conjunto de todos los estados de S a los que esposible llegar desde un estado en s’ siguiendo un arco con la etiqueta x). Como δ es una función, M’ es unautómata finito determinista.

Para cada ruta en M del estado ι al estado sn, que recorre arcos rotulados w1, w2,… wn, existe una ruta enM’ del estado ι‘ al estado s’n que recorre los arcos rotulados w1, w2,… wn, de modo que sn ∈s’n; y a la inversa. Porlo tanto, M y M’ deben aceptar el mismo lenguaje.

Este teorema implica que no se puede mejorar el poder de las técnicas basadas en autómatas finitosdeterministas aunque se permita el no determinismo.



TEOREMA 1.4Para cualquier alfabeto S,{L(M): M es un autómata finito determinista con alfabeto S } =L(M): M es un autómata finito no determinista con alfabeto S }.

Demostración.El hecho de que los lenguajes aceptados por los autómatas finitos no deterministas sean también aceptados

por los autómatas finitos deterministas es una repetición del teorema 1.3. A la inversa, si M=(S, Σ, δ, ι, F) es unautómata finito determinista, entonces el autómata finito no determinista (S, Σ, ρ, ι, F), donde (p, x, q) ∈ ρ si ysólo si δ(p, x)=q, acepta el mismo lenguaje.

1.5 Gramáticas regulares.Una colección de terminales (escritos con minúsculas), de no terminales (entre corchetes o mayúsculas),

junto con un símbolo de inicio y un conjunto finito de reglas de reescritura, se denomina gramática, másprecisamente, gramática estructurada por frases, ya que se basa en la composición de cadenas en términos defrases, donde dada frase está representada por un no terminal. De manera más formal, una gramática se definecomo una cuádrupla de (V,T,S,R), donde V es un conjunto finito de no terminales, T es un conjunto finito determinales,, S (un elemento finito de V) es el símbolo inicial y R es un conjunto finito de reglas de reescritura. Engeneral, los lados derecho e izquierdo de las reglas de reescritura de una gramática pueden ser cualquiercombinación de terminales y no terminales, siempre y cuando el lado izquierdo contenga por lo menos un noterminal.

Se dice que una gramática genera una cadena de terminales si, al comenzar con el símbolo de inicio, sepuede producir esa cadena sustituyendo sucesivamente los patrones que se encuentran en el lado izquierdo de lasreglas de reescritura de la gramática con las expresiones correspondientes a la derecha, hasta que sólo quedenterminales.

Si los terminales de una gramática G son símbolos del alfabeto S, decimos que G es una gramática delalfabeto S. En este caso, las cadenas generadas por G son en realidad cadenas de S *.Por lo tanto, una gramática Gde un alfabeto S especifica un lenguaje de S que consiste en las cadenas generadas por G; a este lenguaje se lerepresenta como L(G). Se define como gramática regular a aquella que cumple:

• El lado izquierdo de cualquier regla de reescritura es un sólo no terminal.• El lado derecho debe ser un terminal seguido de un no terminal, o un sólo terminal, o la cadena vacía

(l).

TEOREMA 1.5Para cada alfabeto S {L(G): G es una gramática regular de S }= { L(M):M es un autómatafinito de S }. (Es decir, los lenguajes generados por las gramáticas regulares son exactamenteaquellos que reconocen los autómatas finitos.)

DemostraciónSi G es una gramática regular de S, se puede convertir en una gramática regular G’ que genere el mismo

lenguaje pero que no contiene reglas de reescritura cuyo lado derecho consiste en un solo terminal. Se puededefinir M como el autómata finito no determinista (S, S, r, i, F), donde S es la colección de no terminales de G’, iies el símbolo inicial de G’, F es la colección de no terminales de G’ que aparecen en el lado izquierdo de algunaregla l, y r consiste en la tripleta (P, x, Q) para el cual G’ contiene una regla de reescritura de la forma P à xQ. Ala inversa, si M es el autómata finito no determinista (S, S, r, i, F), entonces se puede definir G’ como lagramática regular de S para la cual los no terminales son los estados de S, el símbolo inicial es ii y las reglas dereescritura son de la forma PàxQ si (P, x, Q) está en rr y Qàl está en F.

En ambos casos, L(M) = L(G’) ya que la derivación de una cadena de la gramática G’ correspondedirectamente a una ruta en el diagrama de transiciones de M que conduce del estado inicial a un estado deaceptación y viceversa.

Expresiones regulares.Si disponemos de una colección de bloques que contiene el lenguaje vacío Ø y todos los lenguajes de

cadenas simples con longitud uno, se pueden construir lenguajes más complejos a partir de los más básicos.

UNION: La técnica más directa es combinar dos lenguajes, utilizando la operación unión. La unión de doslenguajes regulares produce un lenguaje regular. El diagrama de transiciones se consigue mediante los siguientespasos:

• Dibujar un nuevo estado inicial. Si y sólo si uno de los estados iniciales de los lenguajes originales erade aceptación, éste también lo será.



• Para cada estado que sea punto de destino de un arco de alguno de los estado iniciales originales, sedibuja un arco a partir del estado original creado en el punto anterior, con la mismo etiqueta.

• Eliminar la característica de inicio de los estados iniciales originales.CONCATENACION: Esta técnica para combinar dos lenguajes recopila todas las cadenas formadas al

concatenar una cadena del primer lenguaje y una del segundo. La colección de cadenas así lograda se denominaconcatenación, se representa como L1oL2; la concatenación de dos lenguajes regulares también produce un lenguajeregular. El diagrama de estados de la concatenación de dos lenguajes se consigue de la siguiente forma:

• Desde cada estado de aceptación de L1 se dibuja un arco hacia cada estado de L2 que sea destino de unarco del estado inicial de L2. La etiqueta será la misma que el correspondiente arco de L2.

• Los estados de aceptación de L1 seguirán siéndolo si y sólo sí el estado inicial de L2 es también unestado de aceptación.

ESTRELLA DE KLEENE: Amplia un sólo lenguaje en vez de combinar dos. Esto se logra formandotodas las concatenaciones de cero o más cadenas del lenguaje que se amplia. Se representa mediante un asteriscosuperíndice *. La estrella de Kleene genera la cadena vacía {λ} a partir de Ø. La construcción de un diagrama detransiciones que acepte la estrella de Kleene es:

• Dibujar un nuevo estado inicial y conectarlo al diagrama inicial. Se elimina la designación de inicialdel estado inicial original

• El nuevo estado inicial se conecta a cada uno de los estados destinos del estado inicial original,rotulándolos con la misma etiqueta.

• El nuevo estado inicial se marca como estado de aceptación.• Se añade un arco de cada estado de aceptación a cada estado que es destino de un arco del estado

inicial. Se rotulan con la etiqueta que corresponde al arco del estado inicial.

Dado un alfabeto particular y usando las operaciones unión, concatenación y estrella de Kleene, se puedeconstruir muchos lenguajes. Una expresión regular (para un alfabeto Σ) se define como sigue:

a. Ø Es una expresión regular.b. Cada miembro de Σ es una expresión regular.c. Si p y q son expresiones regulares también lo es ( p q∪ )

d. Si p y q son expresiones regulares también lo es ( p qo )

e. Si p es una expresión regular también lo es p*.

TEOREMA 1.6Dado un alfabeto Σ, los lenguajes regulares de Σ son exactamente los lenguajes representadospor las expresiones regulares de Σ.

Demostración.Todo lenguaje que contenga Ø, y todo lenguaje que contenga sólo una cadena de longitud uno es regular.

La unión y concatenación de lenguajes es regular. La estrella de Kleene también lo es, luego un lenguajerepresentado por una expresión regular es regular. Además se puede demostrar que cualquier lenguaje aceptadopor un autómata finito puede representarse con una expresión regular.

Como conclusión se puede afirmar que los lenguajes regulares son los aceptados por Autómatas FinitosDeterministas, Autómatas Finitos no Deterministas, lenguajes generados por gramática regulares y los lenguajesrepresentados por expresiones regulares.



2. AUTÓMATAS DE PILA Y LENGUAJESINDEPENDIENTES DEL CONTEXTO

2.1 Autómatas de pila.

DEFINICIÓN DE LOS AUTÓMATAS DE PILA.Un autómata de pila cuenta con un flujo de entrada y un mecanismo de control que puede encontrarse

entre uno de un número finito de estados. Uno de estos estados se designa como inicial y por lo menos un estado sedesigna como estado de aceptación. Cuenta también con una pila en donde almacena información para recuperarlamás tarde. Los símbolos que pueden almacenarse en esta pila (símbolos de pila de la máquina) constituyen unconjunto finito que puede incluir algunos o todos los símbolos del alfabeto de la máquina y alguno adicional que seusa como marcas internas ( # es el indicador de pila vacía).

Las transiciones de un autómata de pila se representan con la notación (p, x, s; q, y) donde p es el estadoinicial, x es el símbolo que se lee de la entrada, s el símbolo que se extrae de la pila, q el nuevo estado e y elsímbolo que se inserta en la pila.

Para representar la colección de transiciones disponibles para un autómata de pila, es conveniente utilizarun diagrama de transiciones. Los arcos que representan transiciones tiene una etiqueta de la forma x, y; z ( símbololeído de la entrada [x], símbolo leído de la pila [y] y símbolo insertado en la pila [z]). Formalmente un autómata depila es una séxtupla de la forma (S, Σ, Γ, Τ, ι, F) donde:

a. S es una colección finita de estados.b. Σ es el alfabeto de la máquina.c. Γes una colección finita de símbolos de pila.d. Τ es una colección finita de transiciones.e. ι (un elemento de S) es el estado inicial.f. F (un subconjunto de S) es la colección de estados de aceptación.

AUTÓMATAS DE PILA COMO ACEPTADORES DE LENGUAJESLos autómatas de pila son no deterministas. Nos referimos a todas las cadenas aceptadas por el autómata

de pila M como el lenguaje aceptado por la máquina, representado por L(M). L(M) no es cualquier colección decadenas aceptadas por M, sino la colección de todas las cadenas que acepta M.

Se puede obtener una importante clase de máquinas restringiendo las transiciones disponibles para unautómata de pila a las de la forma (p, x, λ; q, λ). Esta forma ignora la pila del autómata y sus actividades dependensólo del estado y la entrada actual, es decir, es de la clase de autómatas finitos. Por ello, los lenguajes aceptados porlos autómatas de pila incluyen los lenguajes regulares.

Los autómatas de pila pueden aceptar lenguajes que no pueden aceptar los autómatas finitos (por ejemplo{xnyn: n ∈N}.

TEOREMA 2.1Para cada autómata de pila que acepta cadenas sin vaciar su pila, existe un autómataque acepta el mismo lenguaje pero que vacía su pila antes de llegar a un estado deaceptación.

Las modificaciones para conseguir lo expuesto en el teorema 2.1 son:1. Eliminar la designación de “inicial” del estado inicial de M. Añadir un nuevo estado inicial y una

transición de éste estado al anterior, insertando en la pila el símbolo # (que no se encontraba en Γ ).2. Eliminar la característica de aceptación de cada estado de aceptación de M. Añadir un estado p, con

una transición de cada uno de los antiguos estados de aceptación a p sin leer, extraer o insertar unsímbolo (λ, λ, λ).

3. Para cada x en Γ (sin incluir #), introducir la transición (p, λ, x; p, λ).4. Añadir un estado de aceptación q y la transición (p, λ, #; q, λ).

Las dos máquinas aceptarán las mismas cadenas; con la diferencia de que el autómata basado en el nuevodiagrama no aceptará la cadena sin tener vacía la pila.



2.2 Gramáticas independientes del contexto.Las gramáticas independientes del contexto, a diferencia de las gramáticas regulares, no tienen

restricciones con respecto a la forma del lado derecho de sus reglas de reescritura, aunque requieren que el ladoizquierdo sea un solo no terminal. El término “independiente del contexto” refleja que, como el lado izquierdo decada regla de reescritura únicamente puede contener un solo no terminal, la regla puede aplicarse sin importar elcontexto donde se encuentre dicho no terminal.

El orden en el que se apliquen las reglas de reescritura (derivación por la izquierda o por la derecha) noafecta la determinación de si una cadena puede generarse a partir de una gramática independiente del contexto. Unárbol de análisis sintáctico no es más que un árbol cuyos nodos representan terminales y no terminales de lagramática, el nodo raíz es el símbolo de inicio y los hijos de cada nodo no terminal son lo símbolos que reemplazana ese no terminal en la derivación (ningún símbolo terminal puede ser un nodo interior del árbol ni ningún símbolono terminal puede ser una hoja). Cuando se aplican unas reglas de reescritura, el orden de aplicación sólo refleja elorden de construcción de las ramas del árbol. El orden de construcción de las ramas no afectará a la estructurafinal del árbol, ya que cada rama es independiente de las demás.

Cualquier gramática regular es una gramática independiente del contexto, por ello las gramáticasindependientes del contexto generan una mayor colección de lenguajes que las gramáticas regulares. Los lenguajesgenerados por gramáticas independientes del contexto se denominan lenguajes independientes del contexto.

GRAMÁTICAS INDEPENDIENTES DEL CONTEXTO Y AUTÓMATAS DE PILASe pueden considerar las transiciones que insertan más de un símbolo en la pila como (p,a,s;q,xyz); que

quiere decir, que se insertan en la pila los símbolos x,y,z (en ese orden), de manera que después de realizar latransición, x se hallará en la cima de la pila. Esto sólo es una convención sobre notación ya que no añade ni restacapacidades a la máquina.

TEOREMA 2.2Para cada gramática G independiente del contexto, existe un autómata de pila M tal queL(G) = L (M).

Dada una gramática G independiente del contexto, se construye un autómata de pila M de la manerasiguiente:

1. Designar el alfabeto de M como los símbolos terminales de G, y los símbolos de pila de M como lossímbolos terminales y no terminales de G, junto con el símbolo especial # ( se puede suponer que # noes un símbolo terminal o no terminal de G).

2. Designar los estados de M como ii, p, q y ƒ, donde ii es el estado inicial y ƒ es el único estado deaceptación.

3. Introducir la transición (ι,λ,λ;p,#).4. Introducir la transición (p,λ,λ;p,S), donde S es el símbolo inicial de G.5. Introducir una transición de la forma (p,λ,Ν;p,w) para cada regla de reescritura N àw en G (w puede

ser una cadena de cero o más símbolos, incluyendo terminales y no terminales, es decir, que en unatransición se puede insertar uno o más símbolos en la pila).

6. Introducir una transición de la forma (q,x,x;q,λ) para cada terminal x de G (es decir, para cadasímbolo del alfabeto de M).

7. Introducir la transición (q,λ,#;ƒ,λ).

Un autómata de pila construido de esta manera analizará una cadena de entrada marcando el fondo de lapila (#), luego inserta el símbolo inicial de la gramática y después entra en el estado q. De ahí y hasta que aparezca(#) en la cima de la pila, el autómata extraerá un no terminal de la pila y la reemplazará con el lado derecho de unaregla de reescritura aplicable, o extraerá un terminal de la pila a la vez que lee el mismo terminal de entrada. (Esteautómata realiza la derivación por la izquierda.). Por lo que el autómata acepta exactamente el mismo lenguaje quegenera la gramática.

TEOREMA 2.3Para cada autómata de pila M, existe una gramática G independiente del contexto tal que L(M)=L(G).

FORMA NORMAL DE CHOMSKYUna de las ventajas de clasificar los lenguajes en función de su gramática es que estas clasificaciones

proporcionan detalles con respecto a las estructuras de cadenas que pueden aparecer en los lenguajescorrespondientes.

Cualquier lenguaje independiente del contexto que no contiene la cadena vacía se puede generar pormedio de una gramática independiente del contexto que no tenga reglas λ.



TEOREMA 2.4Si L es un lenguaje independiente del contexto que no contiene la cadena vacía, entoncesexiste una gramática independiente del contexto tal que L(G)=L y el lado derecho decualquier regla de reescritura en G consiste en un solo terminal o exactamente dos noterminales.

Se dice que una gramática cuyas reglas de reescritura se adhieren a las restricciones del teorema 2.4 tienela forma normal de Chomsy. Por ejemplo la gramática:

S à XMM à SYX à xY à y

cuyo símbolo inicial es S tiene la forma normal de Chomsky.

En resumen, el teorema 2.4 indica que cualquier lenguaje independiente del contexto que no contenga lacadena vacía puede ser generado por una gramática independiente del contexto que tenga la forma normal deChomsky.

Eliminación de las producciones vacías.1. Se buscan todos los no terminales que nos pueden llevar a la palabra vacía2. Se agregan a la gramática todas las reglas de reescritura, resultado de eliminar las ocurrencias

de los no terminales que generan la palabra vacía.3. Hecho esto ya no se necesitan las reglas λ.

Paso a la forma normal de Chomsky.4. Cada terminal es sustituido por un nuevo no terminal, y se añaden las reglas de reescritura

que llevarán del nuevo no terminal al terminal.5. Las reglas de reescritura con más de dos no terminales se reemplaza por un encadenamiento

de reglas de reescritura con sólo dos no terminales.6. Se evita la aparición de un solo no terminal por sustitución.

Aunque este procedimiento se limita a un subconjunto de los lenguajes independientes del contexto (losque no generan la cadena vacía), esta caracterización sigue siendo bastante general. De hecho si un lenguajeindependiente del contexto contiene λ, se puede encontrar una gramática independiente del contexto que casi tengala forma normal de Chomsky pero que aún genera L. Para lograrlo:

1. Se encuentra la gramática G independiente del contexto con la forma normal de Chomsky quegenere el lenguaje L - {λ}.

2. Modificar G agregando un nuevo no terminal S’ que se convierte en el símbolo inicial de lanueva gramática.

3. Se añade la regla S’ à λ, para que la nueva gramática genera λ.4. Para cada regla de G cuyo lado izquierdo consiste en el antiguo símbolo inicial de G, se

agrega una nueva regla en donde se sustituye con el nuevo no terminal S’ en ese ladoizquierdo.

2.3 Límites de los autómatas de pila.

Alcance de los lenguajes independientes del contexto.El siguiente lema, conocido como lema del bombeo muestra cómo en algunos lenguajes independientes del

contexto pueden producirse cadenas “bombeando” (ampliando) porciones de otras cadenas.

TEOREMA 2.5Si L es un lenguaje independiente del contexto que contiene un número infinito decadenas, entonces debe existir en L un cadena que tenga la forma svuwt, dondes, v, u, w y t son subcadenas, por lo menos una de v y w no es vacía, y vnuwnt está

en L para cada n ∈ +N .

Como consecuencia tenemos que el lenguaje {xn yn zn:n ∈ +N } no es independiente del contexto. Dehecho, tiene una longitud infinita de cadenas, pero no existe en el lenguaje cadena alguna que tenga un segmentocon las posibilidades de repetirse según lo establecido por el teorema y aún así producir cadenas en el lenguaje.



Una cadena del tipo {xn yn zn: n ∈ +N } sería por ejemplo una palabra subrayada siendo x el carácter, y elretroceso y z los símbolos del subrayado.

Autómatas de pila deterministas.De manera general, un autómata de pila determinista es un autómata de pila en el cual es aplicable una y

sólo una transición, en cualquier instante una autómatas de pila determinista se define como el autómata de pila(S,Σ,Γ,Τ,ι,F) tal que para cada tripleta (p,x,y) en S× Σ × Γ existe una y sólo una transición en T de la forma(p,u,v;q,z) donde (u,v) está en {(x,y), (x,λ), (λ,y), (λ,λ)}, q está en S y z está en Γ.

TEOREMA 2.6Existe un lenguaje independiente de contexto que no es el lenguaje aceptado por ningúnautómata de pila determinista.

Este teorema nos indica que el requisito de determinismo reduce el poder de los autómatas de pila.Tomando en cuenta este teorema, nos referimos a los lenguaje aceptados por un autómata de pila deterministacomo lenguajes independientes del contexto deterministas. El hecho de que esta clase de lenguajes no incluya todoslos lenguajes independientes del contexto indica que el objetivo de construir rutinas deterministas de análisissintáctico basadas en autómatas de pila no se alcanza para todos los lenguajes independientes del contexto, sinoúnicamente en los casos más reducidos, de los lenguajes independientes del contexto deterministas. Además losautómatas de pila deterministas aceptan cadenas sin tener que vaciar la pila, lo que puede desembocar enproblemas.

2.4 Analizadores sintácticos LL(k).

Proceso de análisis sintáctico LL.Una técnica para traducir gramáticas independientes del contexto a autómatas de pila es seguir el proceso

descrito en el teorema 2.2, construcción que produce un autómata de pila que analiza su cadena de entradamarcando antes el fondo de la pila e insertando en la pila el símbolo inicial de la gramática. Luego se aplica:

1. Si la cima de la pila contiene un no terminal de la gramática se reemplaza de acuerdo con unade las reglas de reescritura de la gramática.

2. Si la cima de la pila contiene un terminal, se elimina de la pila si es el que se lee en laentrada. Sino se declara cadena ilegal.

3. Si aparece la marca de fondo de pila, se elimina y se acepta la porción de la cadena de entradaprocesada hasta el momento.

Este proceso analiza la sintaxis de la cadena de entrada produciendo una derivación por la izquierda,conforma lee de izquierda a derecha. Por lo que actúa como un programa obtenido de la traducción directa delautómata. Los analizadores sintácticos desarrollados de esta manera se conocen como analizadores sintácticos LL.La primera L denota que lee su entrada de izquierda a derecha; la segunda indica que el objetivo del analizadorsintáctico es producir una derivación por la izquierda.

Estos analizadores tienen el problema del no determinismo cuando tienen que elegir entre dos posiblesformas de reescribir el mismo no terminal y cuentan sólo con una información. Estas opciones se dan en lasgramáticas que deben generar lenguajes que contienen más de una cadena (una gramática independiente delcontexto que sólo ofrece una manera de reescribir un no terminal sólo puede generar una cadena). Por ello laactividad básica de los analizadores sintácticos LL es predecir cuál de las distintas reglas de escritura se debe usarpara procesar los símbolos de entrada restantes, por ello, a estos analizadores se les llama analizadores sintácticospredictivos.

Aplicando el principio de preanálisis, se pueden resolver muchos de los problemas que se presentan en losanalizadores sintácticos predictivos. Existe una jerarquía para los analizadores sintácticos LL cuya característicadistintiva es el número de símbolos de entrada que comprende su sistema de preanálisis. Estos se llamananalizadores sintácticos LL(k), donde k es un entero que indica el número de símbolos preanalizados.

Tablas de análisis sintáctico.Una tabla de análisis sintáctico para un analizador sintáctico LL(k) es una matriz bidimensional. Las filas

se etiquetan con los no terminales y las columnas con los terminales de la gramática sobre la cual se basa el



analizador sintáctico. Se añade la columna adicional FDC (fin de cadena). El elemento (m, n) de la tabla indica laacción que se debe seguir cuando el no terminal m aparece en la cima de la pila y el símbolo de preanálisis es n.Las tablas de análisis sintáctico simplifican la escritura del programa que efectúa el análisis y permite normalizarsu algoritmo.

2.5 Analizadores sintácticos LR(k).Los analizadores sintácticos LR(k) leen su entrada de izquierda a derecha y construyen la derivación por

la derecha de sus cadenas de entrada utilizando un sistema de preanálisis que comprende k símbolos. Estosanalizadores evitan alguno de los problemas que sufren sus homólogos predictivos.

Proceso de análisis LR.En términos generales un analizador sintáctico LR transfiere símbolos de su entrada a la pila hasta que los

símbolos superiores de la pila sean iguales al lado derecho de alguna regla de reescritura de la gramática en que sebasa el analizador. Al llegar a este punto el analizador sintáctico puede reemplazar estos símbolos con el noterminal que se encuentra en el lado izquierdo de la regla de reescritura antes de transferir otros símbolos de laentrada a la pila. De esta manera, la pila acumula cadenas de terminales y no terminales, que a su vez sonreemplazados por no terminales “más altos” de la gramática. Por último, todo el contenido de la pila se reduce alsímbolo inicial de la gramática, indicando que los símbolos leídos hasta ese punto forman una cadena que puedederivarse con la gramática.

Con base a este esquema general los analizadores sintácticos LR(k) se clasifican como analizadoressintácticos ascendentes, ya que sus actividades corresponden a la construcción de ocurrencias de no terminales apartir de sus componentes, hasta generar el símbolo inicial de la gramática. Los analizadores sintácticos LL(k) seconocen como analizadores sintácticos descendentes ya que comienzan con el símbolo inicial de la pila y dividenlos no terminales de la pila hasta generar una cadena similar a la entrada.

Un analizador sintáctico LR(k) se basa en un autómata de pila construido a partir de una gramáticaindependiente del contexto, con la excepción de que el autómata se construye con lo pasos siguientes:

1. Establecer cuatro estados: inicial (ι), aceptación (ƒ) y dos llamados p y q.2. Introducir las transiciones (ι, λ, λ; p, #) y (q, λ, #; ƒ, λ), # no pertenece a la gramática.3. Para cada símbolo terminal x en la gramática, introducir la transición (p, x, λ; p, x) que sirve

para que el autómata transfiera a la pila los símbolos de entrada mientras se encuentra en elestado p. Esta transición se denomina operación de desplazamiento.

4. Para cada regla de reescritura N à w (w representa una cadena de uno o más símbolos) queexista en la gramática, introducir la transición (p, λ, w; p ,N). La presencia de estastransiciones significa que si los símbolos de la porción superior de la pila concuerdan con losdel lado derecho de la regla de reescritura, entonces es posible reemplazar estos símbolos conen no terminal de la parte izquierda de esa regla. Transición denominada operación dereducción.

5. Introducir la transición (p, λ,S; q, λ), donde S es el símbolo inicial de la gramática. Es decir,si se han reducido a S los símbolos de la pila, el autómata puede pasar al estado q a la vez queextrae S de la pila.

Implantación de analizadores sintácticos LR(k).Al tratar de convertir los autómatas de pila a un programa aparecen dos problemas. El primero es el

referente al no determinismo (al igual que con los analizadores LL(k)), con los analizadores LR(k) si se presentauna opción, no se sabe si desplazar o reducir. Además, si la opción es reducir, puede haber más de una reducciónposible. Estos problemas se resuelven con las aplicaciones del principio de preanálisis.

El segundo problema viene dado por la interrogación de la pila, ya que para el preanálisis sólo se disponede un elemento de la pila, el de la cima. La solución está en el uso de las tablas de análisis sintáctico LR(k). Lascolumnas de la tabla se rotulan con los símbolos de la gramática (terminales y no terminales) junto con la marca defin de cadena (FDC). Las filas se etiquetan con números que representan símbolos especiales (componentes léxicos,que representan patrones que pueden aparecer en la pila).

El análisis sintáctico de cualquier cadena comienza asignando el valor uno a una variable de símboloespecial e insertando este valor en la pila vacía. Desde este momento a la inserción de un símbolo en la pila lesigue la inserción de un símbolo especial. Es decir, el contenido de la pila alternará entre símbolos terminales, no



terminales y símbolos especiales, donde cada uno de estos últimos representan el patrón de lo que yace debajo deél. Por lo tanto, se puede conocer la estructura interna de la pila observando el símbolo especial de la cima.

Una vez establecido y almacenado en la pila el número especial, se hace referencia a la tabla de análisissintáctico. La fila está determinada por el símbolo especial actual y la columna por el símbolo de preanálisis. Loscasos posibles son:

1. La casilla correspondiente de la tabla está vacía, la cadena se considera inválida, se ejecutauna rutina de error.

2. La casilla contiene la palabra aceptar, la cadena es aceptada y concluye el proceso de análisis.3. La tabla contiene desplazar, lo que indica que debe ejecutarse la operación de desplazamiento,

el siguiente símbolo debe leerse de la entrada (símbolo de preanálisis) y colocarse en la pila; ala variable de símbolo especial se le debe asignar el valor que existe en la casilla de la tabla,junto con la operación de desplazamiento y este nuevo valor de símbolo especial debeinsertarse en la pila; por último, debe actualizarse el símbolo de preanálisis.

4. La tabla contiene una regla de reescritura, lo que indica que se trata de una operación dereducción. Implica la sustitución de una cadena de símbolos de la pila (el lado derecho de laregla de reescritura) con un sólo no terminal (lado izquierdo de la regla). Se debe de eliminardos símbolos de la pila por cada símbolo del lado derecho de la regla de reescritura. Estoelimina cada uno de los símbolos del lado derecho de la regla, así como el valor del símboloespecial que está almacenado encima del símbolo. La cima de la pila contendrá el valor delsímbolo especial que se coloca después de crear la porción inferior (la que queda) de la pila.Este valor es un “símbolo especial temporal” y se inserta encima el no terminal del ladoizquierdo de la regla. Luego, este no terminal se emplea para identificar una columna de latabla de análisis sintáctico, a la vez que el símbolo especial temporal determina una fila. Elvalor que se encuentra en este lugar de la tabla debe asignarse a la variable de símboloespecial e insertarse en la pila.

Con el empleo de una tabla de análisis sintáctico, el analizador LR hace referencia de manera cíclica a latabla hasta encontrar una entrada en blanco o de aceptación.

Tablas de análisis sintácticos LR.La tabla de un analizador sintáctico LR(1) se basa en la existencia de un autómata finito que acepta

exactamente las cadenas de símbolos de la gramática (terminales y no terminales) que conducen a operaciones dereducción. Para conseguirlo no sigue un proceso de prueba y error, sino una secuencia bien definida de eventosguiados por los símbolos que se detectan en la cadena analizada. La idea es comenzar el proceso de análisissintáctico siguiendo la ruta determinada por la cadena de entrada hasta encontrar un estado de aceptación. En estepunto, la ruta recorrida por el autómata finito corresponde al patrón de símbolos que el analizador ha desplazado ala pila. El proceso de análisis retrocede, entonces, por esta ruta recorriendo los símbolos que deben examinarse dela pila durante la operación de reducción. A partir de aquí, el analizador recorre el arco del diagrama detransiciones del autómata finito que tenga la etiqueta equivalente al no terminal colocado en la pila por laoperación de reducción correspondiente. Una vez completada la operación de reducción, los símbolos de la pilacorresponderán una vez más a los símbolos de la ruta que recorre el autómata finito.

Los valores de los símbolos especiales representan los estados del autómata finito. Las casillas dedesplazamiento de la tabla corresponden a los arcos rotulados con terminales, mientras que el símbolo especial quese encuentra en esa casilla representa el estado final del arco. Las casilla de reducción indican que el analizador hallegado a un estado de aceptación en el autómata finito, y proporciona la información necesaria para realizar elproceso de retroceso. Las casilla de las columnas etiquetadas con no terminales permitirán al analizador sintácticoestablecer una nueva dirección en el diagrama después del retroceso.

Comparación entre analizadores sintácticos LR(k) y LL(k).La colección de analizadores sintácticos LR(k) es más poderosa que la de los analizadores LL(k) (por

ejemplo ningún LL(k) puede manejar el lenguaje{ : } { : }x n N x y n Nn n n∈ ∪ ∈ que si es manejable por LR(1)).

Existen lenguajes independientes del contexto que ningún analizador LR(k) puede reconocer. Un analizador LR(k)debe ser determinista y, puesto que su estructura se basa en un autómata de pila, se debe deducir que losanalizadores sintácticos LR(k) sólo pueden analizar los lenguajes que aceptan los autómatas de pila deterministas.

2.6 Comentarios finales.Los lenguajes regulares están contenidos en la clase de los lenguajes aceptados por los autómatas de pila

deterministas que vacían sus pilas antes de aceptar una cadena. Los lenguajes independientes del contexto no son



cerrados para la intersección, es decir, la intersección de los lenguajes independientes del contexto pueden darlugar a un lenguaje no independiente del contexto. Esto implica que los lenguajes independiente del contextotampoco son cerrados para la complementación, es decir, existen lenguajes de Σ* que son independientes delcontexto cuyos complementos en Σ* no lo son. Esto implica que la capacidad de un autómata de pila para aceptarcadenas de un lenguaje no es simétrica con la capacidad para rechazar las cadenas que no se encuentran en ellenguaje (que sería el complemento del lenguaje). Así, existe una importante diferencia entre la capacidad deresponder sí cuando la cadena está en el lenguajes y la capacidad de responder sí o no cuando la cadena está o noen el lenguaje.

Lenguajes generales

Lenguajes independientes del contexto

Lenguajes independientes del contexto determinista

Lenguajes aceptados por autómatas de pila deterministasque vacían sus pilas antes de aceptar una cadena

Lenguajes regulares



3. MÁQUINAS DE TURING Y LENGUAJESESTRUCTURADOS POR FRASES.

3.1 Máquinas de Turing

PROPIEDADES BÁSICAS DE LAS MÁQUINAS DE TURING.La máquina de Turing contiene un mecanismo de control que puede encontrarse en uno de entre un

número finito de estados. Uno se denomina estado inicial, otro estado es el de parada; una vez que llega a esteestado terminan todos los cálculos, por ello no puede tener un estado inicial que sea de parada; por tanto todamáquina de Turing tiene por lo menos dos estados. En esto la máquina de Turing difiere de un autómata finitodeterminista.

Una máquina de Turing puede leer y escribir en su medio de entrada. Las acciones específicas que puederealizar una máquina de Turing son las operaciones de escritura y movimiento. La operación de escritura consisteen reemplazar un símbolo de la cinta por otro y cambiar a otro estado (que puede ser el mismo en el que seencontraba). La operación de movimiento puede comprender mover la cabeza una celda a la derecha o a laizquierda y pasar a un nuevo estado (que puede ser el de partida). La acción que se ejecutará en un momentodeterminado dependerá del símbolo que está en la celda visible para la cabeza, así como del estado actual delmecanismo de control de la máquina.

Siendo Γ el conjunto de símbolos de cinta de una máquina de Turing, S el conjunto de estados y S’ elconjunto de estados que no son el de parada, entonces es posible representar las transiciones de la máquina pormedio de una función de transición de la forma δ: (S’× Γ ) à S × ( { , })Γ ∪ L R , donde se supone que L y R no

pertenecen a Γ. La semántica de esta representación es:a. δ(p, x)=(q, y). Si el estado actual es p y el símbolo actual es x, reemplazar x con el símbolo y y

pasar al estado q.b. δ(p, x)=(q, L). Si el estado actual es p y el símbolo actual es x, mover la cabeza una celda a la

izquierda y pasar al estado q.c. δ(p, x)=(q, R). Si el estado actual es p y el símbolo actual es x, mover la cabeza una celda a la

derecha y pasar al estado q.La cabeza de una máquina de Turing puede rebasar el extremo izquierdo de la cinta, en este caso la

máquina abandonará sus cálculos y se dice que la ejecución de la máquina sufrió una terminación anormal.Las transiciones de una máquina de Turing se pueden representar por medio de un diagrama de

transiciones. Cada uno de los arcos se etiqueta con un par de símbolos separados por una diagonal. El primersímbolo representa el símbolo de la cinta que debe existir en la celda actual para que la transición sea aplicable; elsegundo símbolo es el que se escribirá en la celda actual (si la transición es una operación de escritura), o de locontrario uno de los símbolos, L ó R (si la transición es una operación de movimiento). La máquina de Turing sedefine formalmente como una séxtupla de la forma (S, Σ, Γ, δ, ι, h) donde:

a. S: es una colección finita de estados.b. Σ: es un conjunto finito de símbolos distintos del espacio en blanco, llamado alfabeto

de la máquina.c. Γ: es un conjunto finito de símbolos, incluidos los de Σ, que se conocen como

símbolos de cinta de la máquina.d. δ: es la función de transición de la máquina.e. ι: es un elemento de S llamado estado inicial.f. h: es un elemento de S llamado estado de parada.

3.2 Construcción modular de máquinas de Turing.

COMBINACIÓN DE MÁQUINAS DE TURING.1. Eliminar la característica inicial de los estados iniciales de todas las máquinas, excepto la de aquél

donde se iniciará la máquina compuesta.2. Eliminar todas las características de detención de los estados de parada de todas las máquinas e

introducir un nuevo estado de parada que no pertenezca a ninguno de los diagramas que se combinan.3. Para cada uno de los antiguos estados de parada p y cada x en Γ, dibujar un arco de la siguiente forma:

a. Si la máquina compuesta debe detenerse al llegar a una p con el símbolo actual x, dibujar unarco con la etiqueta x/x de p al nuevo estado de parada.



b. Si al llegar al estado p con el símbolo actual x, la máquina compuesta debe transferir elcontrol a la máquina M=(S, Σ, Γ, δ, ι, h), dibujar un arco con etiqueta x/z de p al estado q deM donde δ(ι, x)=(q, z).

En las grandes aplicaciones es conveniente evitar los detalles interiores de los bloques de construcción apartir de los cuales se construyen máquinas de Turing complejas. Conociendo la tarea de las máquinas máspequeñas se puede obviar como se lleva a cabo la tarea específica y dedicarse sólo al enlace entre ellas. Por ello seevita el uso de diagramas de transiciones detallados y se usa diagramas compuestos. En estos diagramas, cada unode los bloques de construcción se representa como un nodo, las transiciones entre bloques se indican con flechasque se etiquetan con el valor que debe aparecer en la celda actual para que se recorra la flecha. Es decir, si unaflecha del nodo A al nodo B tiene una etiqueta x, entonces la ejecución se transferirá a la máquina B si A llega a suantiguo estado de parada con una x en la celda actual. Debe indicarse con un apuntador el nodo del diagramacompuesto donde debe comenzar la ejecución.

x B

A

C

BLOQUES DE CONSTRUCCIÓN BÁSICOS.Construyendo máquinas individuales que realizan las actividades elementales de la máquina de Turing,

cualquier otra máquina de Turing será composición de estas. Estas máquinas son: mover la cabeza una celda a laderecha, una celda a la izquierda y escribir un símbolo en la celda actual.

x/R

R y/R Máquina que mueve la cabeza a la derecha

∆/R

x/L

L y/L Máquina que mueve la cabeza a la izquierda

∆/L

x/x

x y/x Máquina que escribe un símbolo en la celda actual

∆/xEstas máquinas de Turing realizan estas actividades rudimentarias suponiendo que los símbolos de la cinta son x,y, ∆

3.3 Máquinas de Turing como aceptadores de lenguajes.

PROCEDIMIENTOS DE EVALUACIÓN DE CADENAS.Para evaluar una cadena de algún alfabeto Σ con una máquina de Turing, se registra la cadena en la cinta,

comenzando por la segunda celda (la primera está en blanco). Luego se coloca la cabeza de la máquina en la celdadel extremo izquierdo de la cinta y se pone en marcha la máquina desde su estado inicial. La máquina acepta lacadena si, a partir de esta configuración inicial encuentra el camino hasta su estado de parada.

Al igual que en los demás autómatas, la colección de cadenas aceptadas por la máquina de Turing M, sellama lenguaje aceptado por la máquina y se representa por L(M). Se dice que un lenguaje L, es un lenguajeaceptado por una máquina de Turing, si existe una máquina M, tal que L=L(M).



Las máquinas de Turing son capaces de aceptar lenguajes que no pueden aceptar los autómatas de pila(por ejemplo (xn, yn,zn)). La clase de los lenguajes aceptados por máquinas de Turing contiene propiamente todoslos lenguajes independientes del contexto.

Dada una máquina de Turing M que acepte las cadenas con sólo detenerse, existe otra máquina de TuringM’ que sólo acepta las mismas cadenas si se detiene con la cinta configurada como ∆Y∆∆∆... (Y representa larespuesta afirmativa de aceptación), y viceversa.

Para modificar M, se debe de conseguir que lleve el control de la porción de la cinta que se altera durantela ejecución, para después de los cálculos poder borrarla y escribir el mensaje de aceptación. Para ello se usan lossímbolos especiales # y *. El símbolo # marca el extremo izquierdo de la cinta y el símbolo * marca el extremoderecha de la porción alterada. La máquina modificada deberá comenzar cualquier cálculo con:

à R∆ SR R * L∆L # Res decir, debe desplazarse hacia el extremo derecho de la cinta de entrada y desplazar la cadena una celda a laderecha. Luego debe marcar la primera celda a la derecha de la entrada con el símbolo *, regresar a la celda delextremo izquierdo de la cinta, escribir el símbolo # y ubicar su cabeza sobre el espacio en blanco del extremoizquierdo de la cadena de entrada. Resumiendo su configuración inicial de entrada ∆w∆∆∆...; siendo w la cadenade entrada quedará de la forma # ∆w*∆∆...

Una vez que se han simulado los cálculos de M hasta su estado de parada, la nueva máquina debe borrarsu cinta y escribir el mensaje Y antes de detenerse, lo que se logra con el bloque

à R* à ∆L ¬ # #∆RYL

al final de la máquina modificada.

MÁQUINAS DE TURING DE VARIAS CINTAS.

TEOREMA 3.1Para cada máquina de Turing de varias cintas M, hay una máquina de Turing tradicional(de una cinta) M’ tal que L(M)=L(M’).

Este teorema refuerza la tesis de Turing, al ampliar el dispositivo de memoria añadiendo más cintas no semejora el potencial (poder computacional) de las máquinas de Turing.

MÁQUINAS DE TURING NO DETERMINISTAS.Una máquina de Turing no determinista es similar a una máquina de Turing, con la diferencia de que

quizá no se encuentre totalmente definida o que ofrezca más de una transición aplicable a un par estado-símbolo, oninguna, en cuyo caso pararía los cálculos. Una máquina de Turing no determinista es una séxtupla (S,Σ,Γ,π,ι,h)donde:

S: Es una colección finita de estados.Σ: Es un conjunto finito de símbolos distintos del espacio en blanco (alfabeto de la máquina).Γ: Es la colección finita de símbolos, incluidos los de Σ, símbolos de la cinta.π: Es un subconjunto de ((S-{h})×Γ)×(S×(Γ∪ {L,R}))ι : (Elemento de S) es el estado inicial.h : (Elemento de S) es el estado de parada.

Se dice que una máquina de Turing no determinista M aceptará una cadena w si es posible que M llegue asu estado de parada después de iniciar sus cálculos con la entrada w. Se dice posible ya que si una máquina nodeterminista no alcanza el estado de parada puede ser el resultado de una mala decisión de la máquina, en lugar deuna cadena impropia.

TEOREMA 3.2Para cada máquina de Turing no determinista M, existe una máquina de Turing deterministaD tal que L(M)=L(D).



3.4 Lenguajes aceptados por máquinas de Turing.

Comparación entre lenguajes aceptados por máquinas de Turing y lenguajesestructurados por frases.

Las gramáticas estructuradas por frases no tienen restricción alguna en cuanto a sus reglas de reescritura.Así, tanto el lado izquierdo como el derecho de las reglas de reescritura pueden consistir en cualquier cadena finitade terminales y no terminales, siempre y cuando exista por lo menos un no terminal en el lado izquierdo. Loslenguajes estructurados por frases son precisamente los lenguajes aceptados por máquinas de Turing.

Para poder representar la configuración total de una máquina de Turing en cualquier etapa de sus cálculosse utiliza un nuevo sistema de notación. El contenido de la cinta de la máquina se representa como una cadena desímbolos de cinta encerrados entre corchetes. Primero representamos con [ el extremo izquierdo de la cinta, luegose representa la cadena de símbolos que se encuentran en la cinta, comenzando por la celda del extremo izquierdoe incluyendo por lo menos un espacio en blanco después del último símbolo distinto del espacio, por último secierra la representación con ]. Una cinta que contiene ∆xxyx∆∆∆… se puede representar como [∆xxyx∆] o como[∆xxyx∆∆∆∆∆∆]. Además se incluye el estado actual justo a la izquierda del símbolo actual. Por ejemplo si elestado actual es p y la cinta muestra ∆xxyxx∆∆∆... se representa como [∆xpxyxx∆]. Esta notación ofrece el mediopara expresar los cálculos de una máquina de Turing como secuencia de cadenas de símbolos, donde cada cadenarepresenta la configuración de la máquina en un instante determinado de los cálculos. Si la máquina acepta lacadena w se puede resumir como la secuencia de configuraciones de la máquina que comienza con [ι∆w∆] ytermina con [h∆Y∆], donde ι y h representan los estados de inicio y parada respectivamente.

TEOREMA 3.3Todo lenguaje aceptado por máquinas de Turing es un lenguaje estructurado por frases.

TEOREMA 3.4Todo lenguaje estructurado por frases es un lenguaje aceptado por máquinas de Turing.

ALCANCE DE LOS LENGUAJES ESTRUCTURADOS POR FRASES.TEOREMA 3.5Para cada alfabeto S existe al menos un lenguaje sobre S que no es un lenguajeestructurado por frases.

Podemos generar de manera sistemática una lista de todas las máquinas de Turing, con símbolos de cintaΣ ∪ {∆}, generando primero aquellas máquinas con sólo dos estados de aceptación, después las que tienen tresestados, las de cuatro, … y así sucesivamente. Por tanto existe una cantidad contable de máquinas de Turing. Porotra parte, existe una cantidad finita de cadenas en Σ∗ y debido a ello, es incontable el número de lenguajes que sepueden formar a partir de Σ. Es decir, existen más lenguajes basados en Σ que máquinas de Turing con símbolosde cinta en Σ ∪ {∆}. Esto indica que deben existir lenguajes basados en Σ que no son lenguajes estructurados porfrases.

Estos teoremas indican que existen lenguajes que no tienen bases gramaticales y que las máquinas deTuring sólo reconocen aquellos lenguajes que sí tienen base gramatical. Si un lenguaje no tiene una basegramatical bien definida no es posible procesarlo algorítmicamente. Además, si la mente humana opera ejecutandoalgoritmos, entonces la tesis de Turing indica que existen lenguajes cuya sintaxis no puede analizar la mentehumana. Por otra parte, si la inteligencia artificial se basa en un nivel más poderoso que la ejecución dealgoritmos, entonces la tesis de Turing sugiere que el desarrollo de máquinas verdaderamente inteligentes serásiempre un sueño.

3.5 Más allá de los lenguajes estructurados por frases.

Sistema de codificación de máquinas de Turing.Este sistema de codificación permite representar máquinas de Turing con alfabeto Σ y símbolos de cinta

Σ ∪ {∆} como cadenas que únicamente contienen ceros y unos.• Se colocan los estados de M en una lista cuyo primer elemento es el estado inicial y el

segundo es el estado de parada. El estado j de se representa como una cadena de ceros delongitud j (el primero 0, el segundo 00, …, 000…j..0).

• Los símbolos L y R se representan como 0 y 00 respectivamente, con lo que el símbolo j serepresenta por una cadena de longitud j+2. El primer símbolo se representa por 000.

• El símbolo en blanco se representa con una cadena vacía.



Este sistema nos permite representar los símbolos R y R, los estado de M y los símbolos de cinta de M pormedio de cadenas de ceros. Es decir podemos representar cualquier transición de M como una cadena de ceros yunos. Por ejemplo la transición δ( ι,x) = (h,R) se representará por 01000100100, donde el símbolo inicial es 0, x esel símbolo representado por 000, R se representa por 00 y el estado de parada de la máquina (h) es 00. Como elespacio en blanco se representa con ausencia de cero, la cadena 011001 representa la transición δ( ι,∆) = (h, ∆).

Para representar de esta forma una máquina de Turing, las transiciones incluidas en la lista deben deseguir el siguiente orden: primero se presentan las transiciones que surgen del estado 0 (inicial), luego las que seoriginan del estado 000, etc., hasta incluir todos los estados donde pueden originarse transiciones. Estauniformidad hace más fácil evaluar una cadena de ceros y unos para ver si constituye una representación válida dealguna máquina de Turing determinista (es decir, perfectamente definida).

UN LENGUAJE NO ESTRUCTURADO POR FRASES.Al emplear esta forma de codificación, cada máquina de Turing con alfabeto Σ y símbolos de cinta Σ{∆}

se puede representar como una cadena de ceros y unos, la cual a su vez puede interpretarse como un entero nonegativo en binario. Asociando cada uno de estos enteros a la siguiente máquina:

∆

¬∆Tenemos de esta manera una función de Ν sobre las máquinas de Turing con alfabeto Σ y símbolos de

cinta Σ ∪ {∆}. Se emplea la notación Mi para representar la máquina que esta función relaciona con el entero i.En base a esta función se puede construir otra máquina de alfabeto Σ∗, sobre la colección de máquinas de

Turing descrita anteriormente, basta con asociar una cadena w de Σ∗ con la máquina M|w|, donde |w| representa lalongitud de w. Si se define el lenguaje L0 como el subconjunto {w: Mw no acepta w}de Σ∗; una cadena w de Σ∗ sehalla en L0 si y sólo sí ésta no es aceptada por su máquina Mw correspondiente.

Se analiza si la cadena w0 existe o no en L(Mw0) [tiene que estar o no estar]. Con la definición de L0, sesabe que w0 ∈L(Mw0) implica que w0 ∉L0, y que w0 ∉ L(Mw0) implica que w0 ∈L0. Sin embargo ambos enunciadoson contradictorios, por lo que se concluye que el lenguaje L0 no es aceptado por su máquina de Turing.

MÁQUINAS DE TURING UNIVERSALES.Si se demuestra que el complemento de L0,es decir, el conjunto {w:Mw acepta w} es aceptado por

máquinas de Turing, se demuestra también que la capacidad de una máquina de Turing para aceptar un lenguajeno es simétrica con la capacidad para rechazar el complemento del lenguaje. Es decir, que hay casos en que sepuede construir una máquina de Turing que identifique las cadenas de un lenguaje, pero no se puede construir unamáquina que identifique las cadenas que no están en el lenguaje.

Una máquina de Turing universal no es más que una máquina programable, es decir, puede simularcualquier otra máquina dependiendo. Un programa de una máquina de Turing universal consta de la versióncodificada de la máquina de Turing que se desea simular, seguida de la cadena de símbolos a evaluar, tambiéncodificada entre 1’s, siguiendo el procedimiento de codificación de máquinas. La máquina de Turing universalpuede detectar el final de la codificación de la máquina simulada ya que la siguiente transición no empieza por uncódigo de estado sino con un 1.

COMPARACIÓN ENTRE LENGUAJES ACEPTABLES Y DECIDIBLES.Mediante una máquina de Turing universal, se puede construir una máquina que acepte el complemento

del lenguaje L0. Primero se construye una máquina de Turing Mpre que procesa una cadena de entrada w de Σ∗de lasiguiente manera:

1. Genera una cadena de ceros y unos que representa la máquina Mw.2. Coloca la cadena obtenida en la cinta de la máquina, seguida por la versión codificada de w.

Se puede construir entonces una máquina que acepta el complemento de L0 formando la máquinacompuesta àMpre à Tu, que dada una cadena de entrada w, aplicaría Mw a w y se detendría si y sólo si seencontrara que Mw acepta w. De esta forma se acepta el lenguaje L1={w:Mw acepta w}, que es el complemento deL0.



Como consecuencia, se puede afirmar que no es obligatorio que el complemento de un lenguaje aceptadopor máquinas de Turing sea también aceptado por máquinas de Turing. Esta falta de simetría tiene repercusionesimportantes. Quiere decir que la capacidad para aceptar un lenguaje no es simétrica con la capacidad para rechazarsu complemento. Es decir, que existe un lenguaje L para el cual podemos construir una máquina de Turing queresponda afirmativamente al recibir entradas de L, pero no se puede construir una máquina de Turing queresponda afirmativamente a todas las cadenas de L y negativamente en caso contrario. Los lenguajes que cumplenesta condición son lenguajes decidibles, ya que una máquina de Turing puede decidir si una cadena se encuentra ono en el lenguaje, en vez de sólo aceptar las cadenas que pertenecen al mismo Todos los lenguajes independientesdel contexto son decidibles. Existen también lenguajes decidibles que no son independientes del contexto, porejemplo {xn,yn,zn}.

Esta terminología no es universal, en otros contextos un lenguaje aceptado por máquinas de Turing seconoce como lenguaje enumerable recursivamente y los lenguajes recursivos como lenguajes decidibles pormáquinas de Turing.

EL PROBLEMA DE LA PARADASe representa con ρ(M) una máquina de Turing M representada con una cadena de ceros y unos.

Centrando la atención en las máquinas con alfabeto {0,1} y símbolos de cinta {0,1,∆}, entonces la cadena decódigo ρ(M) se podría usar como entrada para la misma máquina M. No interesa si esta forma de usar M tienerelación con el fin con el cual se diseña originalmente M. Lo único que importa es si M se detiene, o no, cuandoinicia su operación con ρ(M) como entrada. Si se detiene se dice que M es autoterminante. De esta forma cualquiermáquina de Turing con alfabeto{0,1} y símbolos de cinta {0,1,∆}, es autoterminante o no autoterminante.

Se define un lenguaje Lh de {0,1}* como { ρ(M): M es autoterminante}. Para asegurar que Lh es decidiblepor máquinas de Turing, se requiere la capacidad de detectar si una cadena de {0,1}* es la versión codificada deuna máquina autoterminante, es decir, el problema de decidir si una máquina se para cuando se le aplica unaentrada específica. El problema de decisión sobre Lh se conoce como problema de la parada. Según Turing Lh no esdecidible

Comentarios finales.

Variante de la jerarquía de lenguajes de Chomsky.

Lenguajes generales

Lenguajes estructurados por frases

Lenguajes decidibles por máquinas de Turing.

Lenguajes independientes del contexto.

Lenguajes independientes del contexto deterministas.

Lenguajes regulares

teoría autómatas

Documents