IEEE

Teoría de Autómatas y Lenguajes Formales.

Ejercicios de Lenguajes Regulares


 
Teoría
 de
 Autómatas
 y
 
Lenguajes
 Formales
 
Ejercicios
 de
 
Lenguajes
 Regulares
 

Autores:
Araceli Sanchis de Miguel
Agapito Ledezma Espino
Jose A. Iglesias Martínez
Beatriz García Jiménez
Juan Manuel Alonso Weber

* Algunos ejercicios están basados enenunciados de los siguientes libros:
• Enrique Alfonseca Cubero, Manuel Alfonseca Cubero, Roberto Moriyón
Salomón. Teoría de autómatas y lenguajes formales. McGraw-Hill (2007).
• Manuel Alfonseca, Justo Sancho, Miguel Martínez Orga. Teoría de lenguajes,
gramáticas y autómatas. Publicaciones R.A.E.C. (1997).
• Pedro Isasi, Paloma Martínez y Daniel Borrajo. Lenguajes, Gramáticas y
Autómatas. Unenfoque práctico. Addison-Wesley (1997).

1

Teoría de Autómatas y Lenguajes Formales.

Ejercicios de Lenguajes Regulares

1. Obtener el AFD mínimo equivalente a cada una de las siguientes gramáticas,
describiendo las transformaciones intermedias: G → AFND → AFD → AFD
mínimo.
a)

c)

GA = ({a,b,c}, {S,A,B}, S, PA)
PA = { S ::= aA | bB | c
A ::= aB | b | cA
B ::= a | bA | c
}
GC =({a,b,c}, {S,A,B,C,D}, S,
PC)
PC = { S ::= aA
A ::= aA | bB | a
B ::= bB | bC | b
C ::= bC | cD | bB
D ::= bC | bB |cC
}

b)

GB = ({a,b,c}, {S,B,C,E}, S, PB)
PB = { S ::= a | aS | aB | cC
C ::= c
B ::= bE | b
E ::= bB | b
}
d)
GD = ({c,f,d}, {A,B,C,D,E,F}, A,
PD)
PD = { A ::= cB | cE | f | fC
B ::= cB | fD | dE
C ::= cA
D ::= cD | fD
E ::= cE | fF | dF
F ::= cF | fF
}2. Sea el alfabeto de terminales {a,b}. Desarrollar un autómata que reconozca
cadenas de longitud “3” del lenguaje universal). Obtener la G3 correspondiente a
dicho Autómata.
3. Una puerta blindada dispone de una única cerradura. Para abrirla es necesario
hacer girar en ella tres llaves diferentes (denominadas a, b y c), en un orden
predeterminado, que se describe a continuación:
• Llave a,seguida de llave b, seguida de llave c, o bien
• Llave b, seguida de llave a, seguida de llave c.
Si no se respeta este orden, la puerta se bloquea, y es imposible su apertura; por
ejemplo, si se hace girar la llave a, se retira la misma, se introduce de nuevo y se
hace girar.
Una vez abierta la puerta, la introducción de las llaves en su cerradura, en
cualquier orden, no afecta al mecanismode cierre (la puerta permanece abierta).
Considérese que las denominaciones de las llaves son símbolos de un alfabeto,
sobre el que define el lenguaje L cuyas palabras son las secuencias permitidas de
apertura de la puerta. Por ejemplo, abcbc es una palabra del referido lenguaje.
Se pide:
a) Diseño del autómata AF finito que acepta L.
b) Gramática (limpia y bien formada) que genera laspalabras de L.
4. Dada la ER (b•a*)* que representa a un lenguaje regular, construir un AF que
acepte ese lenguaje regular.

2

Teoría de Autómatas y Lenguajes Formales.

Ejercicios de Lenguajes Regulares

5. Hallar el lenguaje reconocido por el siguiente autómata utilizando ecuaciones
características.

6. Dada la siguiente gramática regular lineal derecha, G= ({0,1},{S,A,B,C},S,P):donde P={ S::= 1A | 1B, A ::= 0A | 0C | 1C | 1 , B ::= 1A | 1C | 1 , C ::= 1}. Se pide
hallar, formalmente la Expresión Regular del lenguaje asociado a dicha gramática.
7. Simplifique la siguiente expresión regular: α = a + a(b+aa)(b*aa)*b* + a(aa+b)*
utilizando las propiedades de equivalencia de las expresiones regulares.
8. Calcular la derivada Dab(α) siendo α = a*ab, utilizando lasdefiniciones de
derivadas de expresiones regulares.
9. Obtenga la gramática para la expresión regular a(aa + b)*.
10. Dada la siguiente expresión regular a*c*(a+b) (cb)*, construir formalmente la
gramática regular equivalente.

3

Teoría de Autómatas y Lenguajes Formales.

Ejercicios de Lenguajes Regulares

SOLUCIONES
 

 
1. Obtener el AFD mínimo equivalente a cada una de las...