Autoevaluacion Autómatas, Gramáticas y Lenguajes II

Considere el siguiente lenguaje L={w {0,1}* | w contiene únicamente dos ceros separados por un número finito de dígitos que es múltiplo de cuatro}. Indique cuál de las siguientes afirmaciones es FALSA: Las cadenas 1000111 y 10100101 pertenecen al lenguaje L. El número de ceros de las cadenas del lenguaje L es siempre dos. Las cadenas 00 y 011110 pertenecen al lenguaje L.

Dado el autómata de la figura. Indicar cuál de las siguientes expresiones es equivalente al autómata : (0 + 1)*(00 + 0(1 + 0)(1 + 0)(1 + 0)(1 + 0)(1(1 + 0)(1 + 0)(1 + 0))*0)(0 + 1)*. (0 (0 + 1) (0 + 1) (0 + 1) 0 (0 + 1)*). (0 + 1)(00 + 0(1 + 0)(1 + 0)(1 + 0)(1 + 0)(1(1 + 0)(1 + 0)(1 + 0))*0) (0 + 1)*.

Sea L el lenguaje representado por la expresión regular (xy ((xy*x)*(x*yx*)) xy) y L' el lenguaje que reconoce el autómata finito de la figura. Indicar cuál de las siguientes afirmaciones es VERDADERA: L c L'. L' c L. L = L'. L n L' no es igual a Conjunto Vacio.

Indicar si son equivalentes los siguientes autómatas. Si. No.

Dado el autómata de la figura determinar si es equivalente a la siguiente 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). Si. No.

Sea L el lenguaje que reconoce el autómata de la siguiente figura: Indicar cuál o cuáles de las siguientes afirmaciones son VERDADERAS (puede haber más de una afirmación verdadera): La expresión regular ((a+b)(a+b)(a+b)(a+b))*(ab+ba)(a+b)* representa al lenguaje L. La expresión regular (a+b)*(ab+ba)(a+b)* representa al lenguaje L. El lenguaje L está formado por cualquier cadena que contenga solamente la letra "a" o solamente la letra "b". El lenguaje L está formado por cualquier cadena que contenga almenos una "a" y al menos una "b". El lenguaje L está formado por todas aquellas cadenas que contengan el par "ab" o el par "ba".

Considere L y Ld con el lenguaje que reconoce los autómatas de la siguiente figura: L c Ld. Ld c L. L = Ld. L no es igual a Ld.

Considere el lenguaje Ld de la siguiente figura. Indicar cuál o cuáles de las siguientes afirmaciones son verdaderas: La expresión regular (a + b)* (ab + ba) (b + a)* representa el mismo lenguaje que Ld. La expresión regular (a*ab + b*ba) (a + b)* representa el mismo lenguaje que Ld. Ninguna de las expresiones regulares de los dos apartados anteriores representa el mismo lenguaje que Ld.

Dado el lenguaje L1 definido por la expresión regular (a + b)*(ab + ba)(a+b)* y el lenguaje L2 representado por la gramática, con símbolo inicial S: S → aS, S → bS, S → aA, S → bD A → bB B → aC, B → bC C → aC, C → bC, C → λ D → aC Indicar cuál de las siguientes afirmaciones es correcta: L1 C L2. L2 C L1. L1 = L2. L1 no es igual a L2.

¿Cuál de las siguientes expresiones regulares representan al lenguaje L1?. Donde L1 está representado por la gramática, con símbolo inicial S, S → bS, S → aF F → bS, F → aF, F → λ. b*aa*(b*a*)*. b*aa*(bb*a*)*. b*aa*(b*aa*)*. bb*aa*(bb*aa*)*.

¿Cuál de las siguientes expresiones regulares representan al lenguaje L1?. Donde L1 está representado por la gramática, con símbolo inicial S, S → bS, S → aF F → bC, F → aF, F → λ C → bS, C → aC. b*aa*(bbb*aa*)*. b*aa*(ba*bb*aa*)*. b*aaa*(ba*bb*aa*)*. b*aaa*(ba*bb*aaa*)*.