Autómatas, Gramáticas y Lenguajes (3/4)

¿Existe algún lenguaje independiente del contexto no regular compuesto por un número finito de palabras?. Si. No.

Dado el lenguaje L1 reconocido por el autómata de la imagen y el lenguaje L2 definido por la gramática: S → xSy S → λ Podemos afirmar: L1 = L2. L1 NO es igual a L2. L1 ⊂ L2. L2 ⊂ L1.

Dado el lenguaje L definido por la gramática S → xS S → Sy S → xy y la siguiente máquina de Turing que reconoce el lenguaje L: (ver imagen) Podemos asegurar que el lenguaje es recursivamente enumerable no regular. Verdadero. Falso.

Sea el lenguaje L = {x^n y^m : n + m es un numero par}. ¿Cuál de las siguientes afirmaciones es verdadera?. El lenguaje L es un Lenguaje Regular. El lenguaje L es un Lenguaje Independiente del Contexto no Regular.

Dada la siguiente gramática regular no determinista, donde A es su símbolo inicial: A → xA A → yA A → xB B → xA B → yA B → xB B → xC C → yD C → xB D → λ D → xB D → yA Podemos construir un autómata finito determinista con sólo 2 estados que reconozca el mismo lenguaje. Verdadero. Falso.

El lema del bombeo aplicado a los autómatas a pila demuestra que el lenguaje L = {x^n y^n z^n: n > 0} no puede ser reconocido por ninguna máquina. Verdadero. Falso.

Sea el lenguaje L = {x^n y^m z^n : con n y m > 0, y m = n/2}. ¿Cuál es la máquina más simple que puede reconocer este lenguaje?. Un autómata finito. Un autómata a pila determinista. Un autómata a pila no determinista. Una máquina de Turing.

La siguiente gramática con símbolo inicial S: S → AB A → Aa A → a B → Bb B → b. Es una gramática regular. Es una gramática independiente del contexto. Ninguna de las anteriores.

Sea L2 = {x^n y^n z^n : n > 0} y sea L1 el lenguaje reconocido por la siguiente máquina de Turing. (ver imagen) ¿Cuál de las siguientes afirmaciones es correcta?. L1 = L2. L1 ⊂ L2. L2 ⊂ L1. L1 no es igual a L2.

Sea L1 el lenguaje generado por la gramática con símbolo inicial S. (Nota:La producción cb → bc indica que cada vez que aparezca la subcadena cb se transforma en la subcadena bc). S → AB A → aAc A → ac B → bB B → b cb → bc y el lenguaje L2 = {a^n b^n c^n : con n > 0}. Podemos afirmar que: L1 = L2. L1 ⊂ L2. L2 ⊂ L1. L1 no es igual a L2.