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

Considere la gramática de símbolos terminales {(,),;,1,2,3}, símbolos no terminales {S,A,E} y producciones: S->(A) A-> A;E I E E->1 I2I3IS La gramática genera listas de elementos que son números o a su vez listas separadas por el símbolo ",".Indicar cuál de las siguientes afirmaciones es verdadera: El lenguaje es regular. El lenguaje es independiente del contexto no regular. No existe una gramática eqyuivalente en Forma Normal de Chomsky.

Dada la siguiente expresión regular: (((a + b)c*(a + b)) + ((ac + ab)*))* y el siguiente autómata finito: Indicar qué valores deben tener Etiqueta-1 y Etiqueta-2 para que el autómata acepte el mismo lenguaje que la expresión regular: Etiqueta-1=a, b Etiqueta-2=a. Etiqueta-1=c Etiqueta-2=a. Etiqueta-1=a Etiqueta-2=a, b. Ninguna de las anteriores combinaciones es válida.

Indicar cuál de los siguientes lenguajes NO es regular: L = {w ∈ {a, b}*|abab es subcadena de w}. L = {w ∈ {a, b}*|w /∈ {a^nb^n} : n > 0}. El lenguaje consistente en las cadenas de caracteres tales que dos a’s están separadas por 4i símbolos para algún entero i ≥ 0.

La estrella de Kleene o clausura de un lenguaje independiente de contexto, ¿es siempre un lenguaje independiente de contexto?. Sí, siempre. No, nunca. Depende de los casos.

Dado el alfabeto Σ = {0, 1}, el lenguaje L se define como L = {w|w contiene un número par de 0’s, o exactamente dos 1’s }. Indicar qué expresión regular genera el lenguaje L: (1*01*01*0*) + (0*10*10*). (1*01*01*)* + (0*10*10*). (10101)* + (0*10*10*).

Indique cuál de las siguientes afirmaciones es verdadera: Dado un alfabeto Σ, para cualquier lenguaje construido sobre Σ existe una máquina de Turing que lo acepta. Dado un alfabeto Σ, cualquier lenguaje construido sobre Σ es recursivamente enumerable. Dado un alfabeto Σ, existen lenguajes construidos sobre Σ que no son recursivamente enumerables y para los cuales no se puede construir una máquina de Turing que los acepte.

Dado el lenguaje L generado por la siguiente gramática: S → xSy | xSyy | z y el siguiente autómata (Nota: Se supone que la pila se encuentra inicialmente vacía. En el diagrama de transiciones algunos arcos tienen una etiqueta en la que el segundo elemento es €. En estos casos se considera que el autómata ejecuta esta transición teniendo en cuenta únicamente el símbolo actual de la cadena de entrada sin inspeccionar el contenido de la cima de la pila. Por tanto, en estas transiciones no se extrae ningún elemento de la pila): Pregunta: ¿Qué función realiza la pila del autómata en relación a las cadenas del lenguaje L?. Lleva la cuenta del número de x’s presentes en las cadenas del lenguaje L. Lleva la cuenta del número de y’s presentes en las cadenas del lenguaje L. Lleva la cuenta del número de z’s presentes en las cadenas del lenguaje L. Lleva la cuenta del número de producciones necesarias para derivar las cadenas del lenguaje L.

Indicar cuál es el autómata más sencillo (con menor capacidad de reconocimiento) que funcione de la siguiente manera. Dada cualquier cadena de x e y, substituya todas las x’s por z’s y devuelva una cadena con todas las y’s al principio y las z’s a continuación. Un autómata finito. Un autómata a pila determinista. Un autómata a pila no determinista. Una máquina de Turing.

Sea L el lenguaje generado por la siguiente gramática: S → xxSyy | xy Indicar cuál de las siguientes afirmaciones es verdadera: L está formado por cualquier cadena que tenga el mismo número de x’s que de y’s. L está formado por cualquier cadena que tenga el mismo número de x’s que de y’s, y que además tenga un número par de símbolos. L está formado por cualquier cadena que tenga el mismo número par de x’s y de y’s. Ninguna de las anteriores afirmaciones es verdadera.

¿Qué podemos afirmar del siguiente autómata?. Es un autómata no determinista que reconoce cadenas de x e y de tamaño mayor o igual a dos. Está mal definido, ya que tiene dos estados de aceptación. No tiene en cuenta la cantidad de símbolos z que se leen de la cadena de entrada. Ninguna de las anteriores.