GUIA PRACTICA DE TEORIA DE AUTOMATAS Y LENGUAJES FORMALES

Lic. Victor Hugo Montaño Quiroga

I Lenguajes Regulares (Expresiones regulares, gramáticas regulares, autómatas de estados finitos) 1.- Dada las siguientes Expresiones Regulares, construir una Gramática Regular y un Autómata de Estados Finitos que genere el mismo lenguaje.

1.- ((a+b+c)•(bb)* + (a+b+c))* 2.- (aaa + aaaaa)* 3.- a• (bac)* •b 4.- b+(a+b+a+) 5.- (aa)* •(bb)* 6.- ((ba)* + (ab)*)*

2.- Construir autómatas de estados finitos determinísticos y gramáticas regulares que generen los siguientes lenguajes:

1.- L = { w ∈ {0,1}* / |w | = 5 y el número de ceros en w es mayor o igual a 2 } 2.- L = { w ∈ {0,1}* / antes y después de cada 0 existe una subcadena 11 } 3.- L = { w ∈ {0,1}* / w no contiene ninguna de las subcadenas: 000 o 111} 4.- L = { w ∈ {0,1}* / w tiene tanto 01 como 10 como subcadenas} 5.- L = { w ∈ {a,b,c}* / w contiene exactamente una a } 6.- L = { w ∈ {a,b,c}* / w = (aaa)*(bbb)* } 7.- L = { w ∈ {a,b,c}* / w no contiene la subcadena bab }

3.- Construir un Autómata de Estados Finitos no Determinista para las siguientes expresiones regulares:

1.- (((11)*+00)* 2.- (1+11+0)* (00)*

4.- Cuáles de los siguientes lenguajes son Lenguajes Regulares (explicar):

1.- {aibj / i=j2} 2.- { aibj / i distinto de j} 3.- { aibj ck/ i=k>j}

5.- Convertir el siguiente Autómata no determinista a determinista A 6.- Ejercicios del libro Elements of the Theory of Computation, Harry Lewis, Christos Papadimitriou:

1). Ejercicios de la sección 2.1.2. 2). Ejercicio 2.1.4. 3) Ejercicio 2.1.5. 4) Ejercicios de la sección 2.2.1 5) Ejercicios de la sección 2.2.2 6) Ejercicios de la sección 2.2.3 7) Ejercicios de la sección 2.3.3 8) Ejercicio 2.4.7. 9) Ejercicio 2.5.5.

7.- Dada la siguiente Gramática Regular G = { {a,b}, {S}, S, { S → aSb, S → ab} ), definir el lenguaje generado por la gramática. 8.- La definición formal de un autómata de estados finitos es: M = ( Q , Σ , δ , q0 , F ) y δ : Q x Σ → Q y L(M) = { w ∈ Σ* / δ* (q0 ,w) ∈ F } Si cambiamos la definición por:

L(M) = {w ∈ Σ* / δ* (q0 ,w) = ... = δ* (P, x) , P ∈ F, x ∈ Σ*} Qué crees que ocurre con el lenguaje, seguirá aceptando el mismo lenguaje ? Analiza con algunos ejemplos, piensa y formula algunos comentarios y conclusiones. 9.- Se define un Autómata de estados finitos Especial como M = ( Q , Σ, δ , q0, F ), donde los elementos fueron definidos para Autómata de estados finitos determinísticos y no determinísticos, y δ es una función desde un subconjunto finito de Q x Σ* → Q . Es un Autómata de estados finitos Especial más parecido a un Autómata de estados finitos determinístico ó a uno no determinístico ? Por qué? 10.- Se dice que un estado q de un Autómata de Estados Finitos M = ( Q , Σ, δ , q0, F) es Alcanzable si existe w ∈ Σ* tal que δ*( q0 ,w) = ... = δ*(q , λ). Demostrar que si

a a

a

b

b a,b

nosotros borramos desde M cualquier estado no-alcanzable, obtenemos como resultado un autómata que acepta el mismo lenguaje. 11.- Demostrar que si L1 y L2 son dos lenguajes generados por autómatas de estados finitos, entonces L1 ∩ L2 es un lenguaje generado por un autómata de estados finitos. 12.- Para cada una de las afirmaciones, decir si es falsa o verdadera, justificar la respuesta. a) Todo subconjunto de un lenguaje regular es regular.

b) Si C es un conjunto de lenguajes regulares, entonces ∪C (la unión) también es regular.

c) Si L1∪L2 es regular y L1 es regular, entonces L2 es regular. 13.- Ejercicios del libro Teoría de Autómatas y Lenguajes Formales, Dean Kelley: 1). Ejercicios del 1.3.1. al 1.3.18 (pag. 40,41)

2). Ejercicio 2.2. 14.- Ejercicios del libro Introduction to Automata Theory, Languages and Computation, John Hopcroft and Jeffrey Ullman:

1). Ejercicio 2.4 2). Ejercicio 2.5 3) Ejercicio 2.8 4) Ejercicio 2.9 5) Ejercicio 2.10 6) Ejercicio 2.11 7) Ejercicio 2.12 8) Ejercicio 2.13 9) Ejercicio 2.14 10) Ejercicio 2.15 11) Ejercicio 2.16 12) Ejercicio 2.17 13) Ejercicio 3.1 14) Ejercicio 3.4

II Lenguajes Libres de Contexto 1.- Cuáles de los siguientes lenguajes son Libres de Contexto? Explique brevemente en cada caso utilizando el análisis de relaciones.

a) L = { am bn cp / m=n ∧ n=p ∧ m=p } b) L = { am bn cp / m≠n ∨ n≠p ∨ m≠p } c) L = { am bn cp / m=n ∧ n=p ∧ m=p } d) L = { an bk cn dk / n,k > 0 } e) L = { ak bk cn dk / n,k > 0 }

f) L = { an bn ck dk / n,k > 0 } 2.- Para cada uno de los siguientes lenguajes, construir un autómata de pila que genere el lenguaje.

a) L = { w ∈ {a,b,c}* / w = am bm cn , n,m ≥ 1 } b) L = { w ∈ {a,b}* / w = am bm ∨ w = am b2m , m ≥ 0 } c) L = { am bn / m ≤ n ≤ 2m } d) L = { w ∈ {a,b,c}* / w = am bm cn ∨ w = am b2m cn, n,m ≥ 0 } e) L = { w ∈ {a,b,c}* / w = am bm cm ∨ w = am b2m c3m , m ≥ 0 } f) L = { w ∈ {a,b}* / # a's = 3 # b's}

3. Demostrar que los Lenguajes Libres de Contexto son cerrados bajo la operación: INIT(L) = { z ∈ X* / existe x ∈ X* , z•x ∈ L} 4.- Demostrar que INIT(L) = INIT(INIT(L)). 5.- Demostrar que los Lenguajes Libres de Contexto son cerrados bajo los operadores: a) SUB(L) = { w / x•w•y ∈ L ∧ x,w,y ∈ X* } b) REVERSO(L) = { w = xn•...• x1 / wR = x1• ... • xn ∈ L, con xi ∈ X} 6.- Indicar si las siguientes proposiciones son verdaderas o falsas. Justificar la respuesta. a) Los lenguajes Libres de Contexto son cerrado bajo la intersección. b) Los lenguajes Libres de Contexto son cerrado bajo la diferencia. c) Los lenguajes Libres de Contexto son cerrado bajo el complemento. 7.- Sea G una gramática Libre de Contexto, w ∈ L(G) y |w| = n. Dar un límite superior e inferior (con demostración) para la longitud de de una derivación de w en G si: a) G está en Chomsky Normal Form. b) G está en Greibach Normal Form. 8.- Si L es un lenguaje Libre de Contexto y R es un lenguaje regular. Es L-R necesariamente Libre de Contexto? Qué puedes decir respecto a R-L? Justificar las respuestas. 9.- Sea G = (X, V, S, P) una gramática libre de contexto. Un símbolo no terminal A ∈ V, se dice Auto-Contenido si y solo si A ⇒* uAv, con u,v (X∪V)*. Demostrar que si G no tiene símbolos no terminales Auto-Contenidos, entonces L(G) es un lenguaje regular. 10.- Indicar si la siguiente proposición es verdadera o falsa. Justificar la respuesta. Si G es una gramática que está en Greibach Normal Form y L = L(G), entonces S ⇒n w, w ∈ X*, donde n < |w| ∨ n > |w|.

11.- Se puede hacer una extensión de un autómata de pila (PDA), de manera que maneje dos pilas en lugar de una sola, entonces se tendría un 2PDA.

a) Definir formalmente un 2PDA (se debe definir todos los conjuntos, configuración, lenguaje aceptado) b) Analizar el poder de estos nuevos autómatas. ¿Pueden reconocer más lenguajes que los libres de contexto? Si la respuesta es si, explicar porque. En caso contrario explicar porque no reconocen más que los lenguajes libres de contexto.

(Ayuda: se puede comenzar analizando con un ejemplo, como ser el lenguaje: L = { w ∈ {a,b,c}* / w = ai b2i c3i , i ≥ 0 } ) 12.- Ejercicios del libro Elements of the Theory of Computation, Harry Lewis, Christos Papadimitriou: a) Ejercicio 3.1.1 b) Ejercicio 3.1.3 c) Ejercicio 3.1.5 d) Ejercicio 3.1.7 e) Ejercicio 3.1.8 f) Ejercicio 3.2.1 g) Ejercicio 3.2.2 h) Ejercicio 3.2.5 i) Ejercicio 3.3.2 inciso a) j) Ejercicio 3.5.1 13.- Ejercicios del libro Teoría de Autómatas y Lenguajes Formales, Dean Kelley: a) Ejercicio 3.9.1 b) Ejercicio 3.9.2 c) Ejercicio 3.9.4

d) Ejercicio 3.4 14.- Ejercicios del libro Introduction to Automata Theory Languajes and Computation, John Hopcroft, Jeffrey Ullman: a) Ejercicios 4.1 – 4.20 b) Ejercicio 5.1 c) Ejercicio 5.2 d) Ejercicio 5.10 15.- Sea G = ( X, V, S, P ) una gramática Libre de Contexto. Un símbolo no terminal A ∈ V se dice Auto-Contenido si y solo si A ⇒* u A v, con u,v ∈ (X ∪ V)*.

a) Dar un algoritmo para ver si un símbolo no terminal, de una gramática Libre de

Contexto dada, es auto-contenido. b) Demostrar que si G no tiene símbolos no terminales auto-contenidos, entonces

L(G) es un lenguaje regular. 16.- Se tiene la siguiente gramática: G = ( {a,b,c,d}, {S,B,C,D}, S, P ) Con P: S → a B C D B → b B B → λ C → b c D → d

a) El algoritmo de Earley no funciona para gramáticas libres de contexto con producciones lambda. Explicar como funcionaria el algoritmo de Earley con producciones lambda (explicar en forma general, no para el ejemplo).

b) Aplicar el algoritmo de Earley extendido a la gramática G, hacer correr por ejemplo para la cadena: “abcd “.

c) Obtener un árbol de derivación para la cadena: “abcd”, a partir de la tabla construida con el algoritmo de Earley. Se debe aplicar un método determinístico, explicar detalladamente como se obtiene el árbol.

II Máquinas de Turing Construir las reglas de transición de una MT (normal), que calcule las siguientes funciones: 1.- f (n) = 3n 2.- f (n,m) = n - m si n ≥ m 0 si m > n 3.- Construir las reglas de transición de una MT (normal), que reconozca el lenguaje:

L = { w•wR / w ∈ {a,b}* } 4.- Demostrar que si una MT M normal (una cinta, un cabezal) acepta cada cadena w ∈ L(M) sin tener que ejecutar más de |w|+1 pasos, entonces L(M) debe ser regular. ( |W| es la longitud de la cadena w) 5.- Describir una MT con 2 cintas y un cabezal, para L = { w ∈ {a,b}* / w = u u v v ∧ u, v ∈ {a,b}* } 6- Describir una MT normal o con alguna extensión, para L ={ w ∈ {a,b}* / w = u uR v vR ∧ u, v ∈ {a,b}*}

7.- Describir una MT (normal), que calcule la función: f (n,m) = n - m Donde n y m son números enteros (positivos o negativos) 8.- Describir una MT (normal), que calcule la función: f (n,m) = n*m (producto) 9.- Describir una MT (normal), que calcule la función: f (n) = n! (factorial) 10.- Describir una MT (normal), que calcule la función: f (n) = log2 n (logaritmo en base 2) Suponer que el resultado siempre es un número entero. 11.- Describir una MT (normal), que calcule la función: f (n) = n2 (elevado al cuadrado) 12.- Describir una MT (normal), que calcule la función: f (n, m) = n DIV m (división entera) 13.- Describir una MT (sólo explicar la idea) que genera el lenguaje L = { an bn / n ≥ 1 }. La máquina tiene que generar en la cinta todos los elementos del lenguaje, el orden no es importante. Es un lenguaje infinito, por lo tanto la máquina nunca para de generar elementos. Al principio la cinta está vacía, no existe ningún parámetro. 14.- Se tiene la siguiente función: f : {a,b,c}* → {1}* donde: f (CE) = n Si el #a’s = #b’s = #c’s en la CE y es igual a n. f (CE) = 0 En otro caso. Describir una MT (sólo explicar la idea) para calcular la función f. 15.- Describir una MT (sólo explicar la idea) que convierta un número decimal en un número binario. Se puede utilizar cualquier extensión de MT o una máquina normal, entonces el primer paso es especificar el tipo de MT y el resultado es un “ALGORITMO” que describa el funcionamiento de la MT. Ejemplo: 10 (decimal) ⇒ 1010 (binario) entrada: B 1 1 1 1 1 1 1 1 1 1 B salida: B 1 0 1 0 B

(en alguna cinta, si se utilizaron múltiples cintas, la salida sólo existe en una cinta) 16.- Construir una MT que genere el lenguaje:

L = { wwR / w ∈ {a,b}* ∧ w = xn ... x1 ∧ (xi = a si i es impar ∨ xi = b si i es par}

La máquina tiene que generar en la cinta, todos los elementos del lenguaje. Es un lenguaje infinito, por lo tanto la máquina nunca para de generar elementos. Al principio la máquina está vacía. 17.- Demostrar: L = L(G), G tiene sólo producciones de la forma u → v con | u | ≤ | v | y si λ ∈ L también existe la producción S → λ y S no aparece en el lado derecho de alguna producción ⇔ L es un lenguaje Sensible al Contexto. 18.- Describir una MT normal o con alguna extensión que reconozca el siguiente lenguaje:

L = { wwRwwR / w ∈ {a,b}* } Demostrar los siguientes teoremas:

a) Una MT (normal) es equivalente a una MT con dos cintas y un cabezal. (Si y solo si)

b) Una MT (normal) es equivalente a una MT con múltiples cintas y un cabezal. (Si y solo si)

c) Una MT (normal) es equivalente a una MT con múltiples cintas y múltiples cabezales. (Si y solo si)

d) Una MT (normal) es equivalente a una MT no determinística. (Si y solo si) 19.- Si deseas más ejercicios, puedes construir o describir Máquinas de Turing con alguna extensión, para los ejercicios propuestos con MT normales, de la presente práctica.