Guia De Teoria De La Computacion

GUIA PRACTICA DE TEORIA DE AUTOMATAS Y LENGUAJES FORMALES
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.2.3.4.5.6.((a+b+c)•(bb)* + (a+b+c))* (aaa + aaaaa)* a• (bac)* •b b+(a+b+a+) (aa)* •(bb)* ((ba)* +(ab)*)*

2.- Construir autómatas de estados finitos determinísticos y gramáticas regulares que generen los siguientes lenguajes: 1.- L = { w 2.- L = { w 3.- L = { w 4.- L = { w 5.- L = { w 6.- L = { w 7.- L = { w ∈ {0,1}* / |w | = 5 y el número de ceros en w es mayor o igual a 2 } ∈ {0,1}* / antes y después de cada 0 existe una subcadena 11 } ∈ {0,1}* / w no contiene ninguna de las subcadenas:000 o 111} ∈ {0,1}* / w tiene tanto 01 como 10 como subcadenas} ∈ {a,b,c}* / w contiene exactamente una a } ∈ {a,b,c}* / w = (aaa)*(bbb)* } ∈ {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,b b a

Aa
a

b

6.- Ejercicios del libro Elements of the Theory of Computation, Harry Lewis, Christos Papadimitriou: 1). 2). 3) 4) 5) 6) 7) 8) 9) Ejercicios de la sección 2.1.2. Ejercicio 2.1.4. Ejercicio 2.1.5. Ejercicios de la sección 2.2.1Ejercicios de la sección 2.2.2 Ejercicios de la sección 2.2.3 Ejercicios de la sección 2.3.3 Ejercicio 2.4.7. 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 estadosfinitos 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

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 dellibro Introduction to Automata Theory, Languages and Computation, John Hopcroft and Jeffrey Ullman: 1). 2). 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) Ejercicio 2.4 Ejercicio 2.5 Ejercicio 2.8 Ejercicio 2.9 Ejercicio 2.10 Ejercicio 2.11 Ejercicio 2.12 Ejercicio 2.13 Ejercicio 2.14 Ejercicio 2.15 Ejercicio 2.16 Ejercicio 2.17 Ejercicio 3.1 Ejercicio 3.4

II Lenguajes Libres de Contexto
1.- Cuáles de...