Autómatas, gramáticas y lenguajes (2/4)

Indicar cuál de los siguientes lenguajes NO es regular: L = {w ∈ {a, b}*|ab y ba son subcadenas de w}. L = {w ∈ {a, b}*|bbb no es subcadena de w}. El lenguaje de cadenas que son prefijos (finitos) de la expansión decimal de π, es decir, L = {3.1 , 3.14 , 3.141 , 3.1415 , . . . }.

Las máquinas de Turing se diferencian de los autómatas finitos y de los autómatas a pila en que. En las máquinas de Turing la cabeza lectora puede retroceder. Las máquinas de Turing pueden escribir sobre su cinta. Las dos afirmaciones anteriores son ciertas.

El resultado de concatenar dos lenguajes independientes de contexto, ¿es siempre un lenguaje independiente de contexto?. Sí, siempre. No, nunca. Depende de los lenguajes que se consideren.

Dado un alfabeto Σ, llamamos L1 al conjunto de lenguajes de Σ aceptados por máquinas de Turing deterministas de una sola cinta, L2 al conjunto de lenguajes de Σ aceptados por máquinas de Turing deterministas con varias cintas y L3 al conjunto de lenguajes de Σ aceptados por máquinas de Turing no deterministas y con varias cintas ¿Cuál de las siguientes afirmaciones es verdadera?. L1 = L2 ⊂ L3. L1 ⊂ L2 = L3. Ninguna de las afirmaciones anteriores es cierta.

5 Sea el alfabeto Σ = {a, b}. Sea L1 el lenguaje reconocido por el autómata de la izquierda y L2 el lenguaje reconocido por el autómata de la derecha. Pregunta: Indicar cuál de las siguientes afirmaciones es verdadera: Uno de los autómatas es determinista y el otro no lo es. El autómata de la izquierda tiene algún estado no accesible. L1 = L2. Ninguna de las anteriores afirmaciones es verdadera.

Dada la siguiente gramática independiente del contexto G: S → aabS | baaS | abaS | aaSb | baSa | aSab | bSaa | aSba | Saab | Sbaa | Saba | abSa | € Indicar cuál de las siguientes afirmaciones es verdadera: Las cadenas que genera G contienen el doble número de a’s que de b’s. Las cadenas que genera G tienen como mínimo una longitud de 2. En las cadenas que genera G todas las a’s aparecen antes que las b’s. Ninguna de las anteriores afirmaciones es verdadera.

Dada la siguiente gramática G: S → A1B A → 0A | € B → 0B | 1B | € y la expresión regular E = 0*1(0 + 1)*. Indicar cuál de las siguientes afirmaciones es verdadera: G y E no pueden generar el mismo lenguaje porque la gramática es independiente del contexto (y por tanto, generará un lenguaje independiente del contexto) y la expresión regular generará un lenguaje regular. Ambos reconocen el mismo lenguaje. Ninguna de las anteriores afirmaciones es verdadera.

Indicar para qué valores de las etiquetas Etiqueta-1 y Etiqueta-2, el autómata de la figura representa el lenguaje {x^n+1y^n : n ≥ 0}. Se supone que inicialmente la pila se encuentra vacía y que el símbolo inicial de la pila es Z0. 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. Etiqueta-1=x, €; z Etiqueta-2=€, z;€. Etiqueta-1=x, €; y Etiqueta-2=€, €;€. No existen valores de Etiqueta-1 y Etiqueta-2 que hagan correcta la solución.

Considere el lenguaje L generado por la siguiente gramática: S → xxSyy | € 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é significado se le puede atribuir al estado par cuando el autómata lee cadenas del lenguaje L?. Se llega al estado par cuando se ha leído un número par de x’s en las cadenas del lenguaje L. Se llega al estado par cuando se ha leído un número par de símbolos en las cadenas del lenguaje L. Se llega al estado par cuando se ha leído un número par de y’s en las cadenas del lenguaje L. Se llega al estado par cuando se ha leído un número impar de x’s en las cadenas del lenguaje L.

Dado el lenguaje L generado por la siguiente gramática: S → xxSyy | xxyy 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- Indicar cuál de las siguientes afirmaciones es verdadera: El autómata no comprueba que haya un número par de y’s en las cadenas del lenguaje L. El autómata no reconoce todas las cadenas contenidas en el lenguaje L. El autómata reconoce todas las cadenas contenidas en el lenguaje L. El autómata no está correctamente definido.