Autoevaluaciones Bloque 2

Autómatas, Gramáticas y Lenguajes

GRADO

EJERCICIOS
BLOQUE II

DE AUTOEVALUACIÓN

| AUTÓMATAS, GRAMÁTICAS Y LENGUAJES

2013-2014

UNIVERSIDAD NACIONAL DE EDUCACIÓN A DISTANCIA|Elena Gaudioso Vázquez,Tomás García Saiz

Autoevaluaciones del Bloque II
1. Considere el siguiente lenguaje L={w

{0,1}* | w contiene únicamente dos

ceros separados por un número finito de dígitosque es múltiplo de cuatro}.
Indique cuál de las siguientes afirmaciones es FALSA:
(a) Las cadenas 1000111 y 10100101 pertenecen al lenguaje L.
(b) El número de ceros de las cadenas del lenguaje Les siempre dos.
(c) Las cadenas 00 y 011110 pertenecen al lenguaje L.
2. Dado el autómata de la figura. Indicar cuál de las siguientes expresiones es
equivalente al autómata :

(a) (0 + 1)*(00 +0(1 + 0)(1 + 0)(1 + 0)(1 + 0)(1(1 + 0)(1 + 0)(1 + 0))*0)(0 + 1)*
(b) (0 (0 + 1) (0 + 1) (0 + 1) 0 (0 + 1)*)
(c) (0 + 1)(00 + 0(1 + 0)(1 + 0)(1 + 0)(1 + 0)(1(1 + 0)(1 + 0)(1 + 0))*0) (0 + 1)*

3.Sea L el lenguaje representado por la expresión regular (xy
(x*yx*))

((xy*x)*

xy) y L' el lenguaje que reconoce el autómata finito de la figura.

Indicar cuál de las siguientes afirmaciones esverdadera:

UNIVERSIDAD NACIONAL DE EDUCACIÓN A DISTANCIA

Autómatas, Gramáticas y Lenguajes

(a) L

L'

(b)L'

L

(c) L = L'
(d)L

L'

4. Indicar si son equivalentes lossiguientes autómatas.

(d) Si
(e) No

UNIVERSIDAD NACIONAL DE EDUCACIÓN A DISTANCIA

|Elena Gaudioso Vázquez,Tomás García Saiz

5. Dado el autómata de la figura determinar si es equivalente a lasiguiente
expresión regular (a + b)(a + b)*. (NOTA: La figura está generada con la
herramienta JFLAP. Recordad que en JFLAP el signo de exclamación ! es
equivalente a epsilon)

(a) Si
(b)No

6.Sea L el lenguaje que reconoce el autómata de la siguiente figura:

UNIVERSIDAD NACIONAL DE EDUCACIÓN A DISTANCIA

Autómatas, Gramáticas y Lenguajes

Indicar cuál o cuáles de las siguientes...