Lenguajes Formales 3, P2

En la descripción instantánea de un autómata a Pila: (q, w, L), ¿Qué significa la w?. w es lo que queda de la entrada, y que falta por analizar ( w Σ* ). q es lo que queda de la entrada, y que falta por analizar ( w Σ* ). L es lo que queda de la entrada, y que falta por analizar ( w Σ* ).

En la representación de una máquina de Turing, ¿Qué elementos no conforman su estructura?. La máquina posee una unidad de control, que puede encontrarse en cualquiera de un conjunto finito de estados. Posee una cinta dividida en casillas (o cuadrados), cada una de ellas puede contener un símbolo de entre un numero finito (de símbolos). Esta cinta es la entrada a la máquina de Turing y teóricamente es infinita hacia la izquierda y a la derecha. La cinta posee una cabeza, denominada cabeza de la cinta que siempre está ubicada en una de las casillas de la cinta, se dice que la máquina de Turing señala dicha casilla. La máquina posee una unidad de estados, que puede encontrarse en cualquiera de un conjunto finito de estados.

En Teoría de la Computación lo importante es buscar la mejor manera de hacer las cosas, a esto se lo llama Computabilidad. Verdadero. Falso.

En un Autómata a Pila, con aceptación por estado final, si al consumir la cadena de entrada el AP está en un estado final, pero la pila no está vacía entonces la cadena no es aceptada. Verdadero. Falso.

En un Autómata a Pila, cuando la cadena de entrada es aceptada por que ha sido leída por completo y se ha llegado a un estado final, sin importar el estado de la pila, decimos que la aceptación es: Por estado final. Por aceptación. Por vaciamiento de pila.

En un Autómata a Pila, si desde el mismo estado, por 2 valores diferentes pasamos al mismo estado, estamos en presencia de: Un AP NO determinista. Un AP determinista.

En una máquina de Turing con cinta semi infinita. La cinta es infinita por derecha. La cinta es infinita por izquierda.

En una máquina de Turing la cinta es: Infinita hacia ambos lados. Infinita hacia derecha. Infinita hacia izquierda.

En una máquina de Turing los símbolos se entrada. Están grabados en la cinta de forma consecutiva, uno en cada celda y símbolos blancos a derecha e izquierda. Están grabados en la cinta de forma secuencial, uno en cada celda y símbolos blancos a derecha e izquierda. Están grabados en la cinta de forma consecutiva, uno en cada celda y símbolos blancos a derecha.

En una máquina de Turing multitareas: Tiene varias cintas. Tiene una cinta. Tiene 2 cintas.

En una máquina de Turing que verifique si una cadena pertenece al lenguaje L ={ w#w | w { 0,1 } }, el alfabeto de entrada debe ser: Σ={ 0, 1, # }. Σ={ 0, 1 }. Σ={ 0, # }.

En una máquina de Turing Universal es: Una maquina programable. Una maquina no programable. Una maquina computacional.

Hablando de derivadas de expresiones regulares podemos afirmar que: "El lenguaje representado por la derivada de una expresión regular…". Es también regular. Es derivable. Es repetitiva.

Hablando de propiedades de las expresiones regulares, si tenemos A.B ¿Qué debemos realizar con A y B? Solo 1 (una) opción es la correcta. Concatenarlos. Ya que el . (punto) es el símbolo que representa la concatenación como operación de lenguajes regulares. Unión. Ya que el . (punto) es el símbolo que representa la unión como operación de lenguajes regulares.

Hablando de propiedades de las expresiones regulares, si tenemos la siguiente expresión A+B ¿A qué propiedad representa el signo +? Solo 1 (una) opción correcta. Unión. Concatenación. Diferenciaa. Clausula.

Indicar cual 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, sustituya todas las x's por las y's y devuelva una cadena con todas las y's al principio y las z's a continuación. Solo 1 (una) opción es correcta. MT. ALA. AP.

Kleene propuso dos teoremas principales que relacionan las expresiones regulares con los autómatas finitos. Selecciona 2 (dos) respuestas correctas. Teorema de Análisis. Teorema de Síntesis. Teorema de Klene. Teorema de Diferencia.

La ambigüedad de una gramática surge cuando derivaciones diferentes generan estructuras diferentes para: La misma cadena. Diferentes cadenas.

La clausura o clausura de Kleene se representa con: Punto. Asterisco. Letra Y.

La concatenación de 2 lenguajes independientes de contexto genera: Un nuevo lenguaje independiente de contexto. Un nuevo lenguaje dependiente de contexto. Un nuevo lenguaje regular.

La ecuación característica del estado inicial es: La expresión regular que describe el lenguaje aceptado por el autómata. La expresión regular que describe el lenguaje no aceptado por el autómata. La expresión regular que describe el lenguaje.

La expresión formal de un autómata a pila es: AP = (Σe, Q, Γ, q0, z0, f, F), donde Γ representa... El alfabeto de símbolos en la pila. El alfabeto de entrada en la pila. El alfabeto de salida de la pila.

La expresión formal de una máquina de Turing es: MT = (Γ, Σ, b, Q, q0, f, F), donde Γ representa... El alfabeto de símbolos en la cinta. El alfabeto de entrada en la cinta. El alfabeto de salida de la cinta.

La expresión formal de una máquina de Turing es: MT = (Γ, Σ, b, Q, q0, f, F), ¿qué representa b?. Un símbolo particular que representa el espacio en blanco. La cinta. Los estados. Estado Inicial.

La función de transición de estados de un autómata a pila se expresa como: f: Q × Σe × Γ -> Q × Γ. f: Q × Σe × Γ. f: Q × Γ -> Q × Γ. f: Q × Σe.

La gramática tipo 2 se utilizan para: Solo 1 opción correcta. Realizar el análisis sintáctico en un compilador. Realizar el análisis léxico en un compilador.

La máquina de Turing universal, ya que cuenta de los mismos componentes y conceptos para entender y resolver lo que le indicamos: (estado valor) (nuevo estado, nuevo valor, dirección). (nuevo estado, nuevo valor, dirección). (estado valor) (nuevo estado, dirección, nuevo valor).

La Teoría de los Autómatas estudia las Maquinas Secuenciales. Verdadero. Falso.

La Teoría de la Compatibilidad se interesa en: Hallar solución a un problema. Hallar Problemas. Hallar programas.

La Teoría de la Complejidad Computacional es una parte de la Teoría de la Computación, a la que le interesa: Los recursos necesarios durante el cálculo para resolver un problema. Revisar los problemas. Revisar las soluciones.

Las expresiones regulares se definen mediante: Un conjunto de casos base y un conjunto de casos recursivos. Un conjunto de casos. Un conjunto de casos recursivos.

Las gramáticas irrestrictas se relacionan con los siguientes tipos de lenguajes de la jerarquía de Chomsky. Tipo 0. Tipo 1. Tipo 2. Tipo 3.

Las gramáticas libres de contexto determinista se relacionan con los siguientes Lenguajes de acuerdo a la jerarquía de Chomsky. Lenguajes independientes del contexto. Los lenguajes recursivamente enumerables están relacionados con las gramáticas irrestrictas. Los lenguajes sensibles al contexto se relacionan con las gramáticas sensibles al contexto. Los lenguajes regulares están relacionados con las gramáticas regulares. Los lenguajes de programación no figuran en la jerarquía de Chomsky.

Las gramáticas regulares se relacionan con los siguientes lenguajes de acuerdo a la Jerarquía de Chomsky. Lenguajes regulares. Lenguajes sin restricciones. Lenguajes dependientes del contexto.

Las gramáticas regulares se relacionan con los siguientes tipos de lenguajes de la jerarquía de Chomsky. Tipo 3. Tipo 2. Tipo 1.

Las gramáticas irrestrictas se relacionan con los siguientes Tipos de lenguajes de la jerarquía de Chomsky. Tipo 0. Tipo 1. Tipo 2. Tipo 3.

Las gramáticas libres de contexto se relacionan con los siguientes tipos de lenguajes de la jerarquía de Chomsky…. Tipo 2. Tipo 1. Tipo 0. Tipo 3.

Las máquinas de Turing se diferencian de los autómatas a pila en que: Las máquinas de Turing la cabeza lectora puede retroceder. Ya que los autómatas finitos no poseen cabeza lectora. Las máquinas de Turing la cabeza lectora no puede retroceder. Ya que los autómatas finitos no poseen cabeza lectora. Las máquinas de Turing tiene cinta.

Las máquinas de Turing se relacionan con las siguientes gramáticas de acuerdo a la jerarquía de Chomsky: Gramáticas irrestrictas. Gramáticas estrictas. Gramáticas dependientes de contexto.

Las operaciones con expresiones regulares tienen las siguientes propiedades: Seleccione las 4 (cuatro) respuestas correctas. La unión es asociativa. La concatenación es asociativa. La concatenación es distributiva respecto a la unión. La unión es conmutativa. λ es el el elemento neutro de la unión.

Las operaciones que permiten definir expresiones regulares son: + (unión), (concatenación), *(cierre o clausura). + (unión), *(cierre o clausura). *(cierre o clausura).

Las transiciones en un autómata a pila dependen de: El estado actual, del símbolo de entrada y del símbolo en el tope de pila. El estado actual. El estado actual y del símbolo de entrada.

Las transiciones que ejecuta un autómata a pila son variantes de las siguientes: Seleccione las 4 (cuatro) respuestas correctas. Leer un símbolo de la entrada. Pasar a un nuevo estado. Extraer un símbolo de la pila. Insertar un símbolo de la pila. Escribir un símbolo de la salida.

Los autómatas a pila reconocen lenguajes Tipo 2 y solo esos. Verdadero. Falso.

Los autómatas a pila se relacionan con las siguientes gramáticas de acuerdo a la jerarquía de Chomsky: Gramáticas libre de contexto. Gramáticas regulares. Gramáticas con contexto.

Los autómatas a pila son herramientas que se usan para: Reconocer lenguajes generados por gramáticas libres de contexto. Reconocer lenguajes generados por gramáticas con contexto. Reconocer lenguajes regulares.

Los autómatas finitos se relacionan con las siguientes gramáticas de acuerdo a la jerarquía de Chomsky. Gramáticas regulares. Gramáticas irrregulares. Gramáticas independientes del contexto.

Los lenguajes aceptados por las máquinas de Turing son generados por gramáticas: Sin restricciones o Tipo 0. Con restricciones o Tipo 1. Regulares.

Los lenguajes aceptados por los autómatas a pila son: Lenguajes independientes del contexto o tipo 2. Lenguajes dependientes del contexto o tipo 1. Lenguajes sin restricciones de tipo 0.

Los lenguajes de tipo 0 en la jerarquía de Chomsky se relacionan con los siguientes Lenguajes. Lenguajes recursivamente enumerables. Lenguajes recursivos. Lenguajes No recursivos.

Los lenguajes de tipo 0 en la jerarquía de Chomsky se relacionan con los siguientes Tipos de máquina abstracta. MT. ALA. AP. AFD.

Los lenguajes independientes del contexto correspondan a autómatas de pila y gramáticas independientes del contexto. Verdadero. Falso.

Los automatas de pila reconocen todos los lenguajes libres del contexto y sólo estos. Verdadero. Falso.

Los ordenadores actuales están basados en el modelo de: La Máquina de Turing Universal. El autómata a Pila.

Los "tokens" se pueden agrupar en dos categorías: cadenas específicas y cadenas no específicas. Indique ¿Cuál de las siguientes no es considerada una cadena especifica?. Los identificadores o las constantes numéricas o de texto, corresponden a las cadenas no específicas. Estas cadenas siempre tienen tipo y valor. Las variables.

Luego de aplicar la operación Homomorfismo a un Lenguaje Regular, ¿Qué obtenemos? Solo 1 (una) opción correcta. Otro lenguaje regular. Debido a que el Homomorfismo es una operación de la propiedad de cierre de los lenguajes regulares, y por definición genera lenguajes regulares. La representación de lenguajes por estructuras formales basados en reglas de producción. La existencia de ordenadores de propósito general.

Marque los 4(cuatro) aspectos de la Informática que han sido influencia por los científicos como Turing, con sus trabajos de investigación sobre los temas de estudio de esta materia: La posibilidad de interpretar programas. La representación de lenguajes por estructuras formales basados en reglas de producción. La dualidad entre software y hardware. La existencia de ordenadores de propósito general. La existencia de otras formas de resolución de problemas.

Operaciones con expresiones regulares tienen las siguientes propiedades: seleccione las 4 (cuatro) respuestas correctas. La concatenación es asociativa. La concatenación es distributiva respecto a la unión. La unión es asociativa. La clausura. La unión es conmutativa.

Partiendo de un autómata finito determinista puede obtenerse: La gramática lineal por derecha que genera el lenguaje reconocido por el autómata. La gramática lineal por izquierda que genera el lenguaje reconocido por el autómata.

Pensando en el funcionamiento de la máquina de Turing, ¿Qué hace dicha maquina cuando lee esta transición: q1(0,X,D) partiendo del estado inicial q0?. Lee un 0, escribe una X, mueve el cabezal a la derecha y pasa al estado q1. Lee un 1, escribe una X, mueve el cabezal a la derecha y pasa al estado q1. Lee una X, escribe una X, mueve el cabezal a la derecha y pasa al estado q1. Lee un 0, escribe un 1, mueve el cabezal a la derecha y pasa al estado q1.

Pensando en la ambigüedad de las gramáticas y lenguajes, podemos afirmar que: Las expresiones regulares no son ambiguas. Las expresiones regulares son ambiguas.

¿Qué describe o expresa cada expresión regular (ER)?. Un lenguaje regular. Un lenguaje repetitivo. Una gramática regular.

¿Qué es un autómata?. Es un dispositivo abstracto teórico que recibe como entrada una cadena de estados y los procesa, cambiando de estado y generando una salida. Es un dispositivo abstracto teórico que recibe como entrada una cadena de estados y los procesa. Es un dispositivo abstracto teórico que recibe como entrada una cadena y genera una salida.

¿Qué maquina abstracta se pueden utilizar en el análisis y diseño orientado a objetos? Solo 1 (una) respuesta correcta. MT. ALA. AFD.

¿Qué sucede con una máquina de Turing si se encuentra con el problema de la parada? Sólo una opción es la correcta. Estamos ante un problema indecidible. Estamos ante un problema decidible.

Se puede demostrar que, dada una expresión reglar existe un ......... capaz de reconocer el lenguaje que ésta define. Autómata finito. Autómata especial. Autómata irregular. Autómata infinito. Autómata específico.

Sea el lenguaje L = { xkykzm: con k>0 y m par } ¿Cuál es la maquina más simple que puede reconocer este lenguaje?. Un autómata a pila determinista. Un autómata a pila NO determinista.

Sea { L(G1) } el Lenguaje generado por gramática de tipo 1 y { L(G2) } el lenguaje generado por gramáticas de tipo 2, entonces { L(G1) incluido en L(G2) }. Falso. Verdadero.

Sea L = {papa, mama}, ¿Cuál de las siguientes opciones representan la reflexión del mismo? Solo 1 (una) opción correcta. L^R = {mama, papa}. L^R = {amam, apap}.

Sean los conjuntos A = {2,4,6,8} y B = {a,b,c}, indique cuál de las siguientes opciones es una relación sobre AXB. { (2,a), {4,c) }. { (2,2), {4,2) }. { (2,d), {4,d) }.

Seleccione las 2 (dos) opciones correctas. ¿Cuáles de las siguientes afirmaciones son verdaderas en relación a las máquinas de Turing y sus características?. Es el modelo matemático de un autómata que dispone de una cinta de longitud infinita. La máquina de Turing puede leer, escribir o borrar símbolos presentes en la cinta. La máquina de Turing puede escribir o borrar símbolos presentes en la cinta.

Seleccione las 3 (tres) opciones correctas ¿Cuáles de los siguientes autómatas reconocen cadenas de un lenguaje regular?. Autómata finito determinista. Autómata Finito no determinista con transiciones espontáneas. Autómata finito no determinista sin transiciones espontáneas. Autómata a pila.

Seleccione las 3 (tres) opciones correctas ¿Cuáles de los siguientes lenguajes se pueden asociar a algoritmos?. Lenguajes regulares. Lenguajes dependientes del contexto. Lenguajes independientes del contexto. Lenguajes sin restricciones.

Seleccione las 4 (cuatro) opciones correctas. Suponiendo la siguiente expresión regular: 1(01)*, ¿Cuáles de las siguientes expresiones representan el mismo lenguaje?. L= {1 (10) n>=0}. L= {1, 101, 10101, 1010101, ...}. L= {cadenas que presentan la cadena 01 ninguna, una o mas veces pero precedida por 1}. L= {cadenas que inician con 1 y a continuación presentan la cadena 01 ninguna, una o mas veces} . L= {cadenas que inician con 0 y a continuación presentan la cadena 01 ninguna, una o mas veces} .

Seleccione las 4 (cuatro) opciones correctas. ¿Cuáles de las siguientes son expresiones correctas?. El símbolo x (conjunto {x}) es una expresión regular. Los símbolos (A , B) son expresiones regulares siempre que A y B sean expresiones regulares. El símbolo Ø (conjunto vacío) es una expresión regular. El símbolo λ (conjunto {λ}) es una expresión regular. El símbolo λ (conjunto {λ}) no es una expresión regular.

Seleccione las 4 (cuatro) opciones correctas. En un autómata a pila, en cada transición, el autómata cambia de estado y acciona sobre la pila. ¿Cuáles de las siguientes son operaciones validas sobre la pila?. Agregar un nuevo símbolo modificando el tope (push). Cambiar el símbolo del tope por otro símbolo. Eliminar el símbolo en el tope (pop). Dejar el mismo símbolo en el tope. Eliminar pila.

Seleccione las 4 (cuatro) opciones correctas. La expresión formal un autómata a pila incluye: Z0: Símbolo inicial de la pila. q0: Estado inicial. Γ: Alfabeto de símbolos en la pila. Q: conjunto finito de estados. q1: Estado inicial.

Seleccione las 4 (cuatro) opciones correctas. La expresión formal de una máquina de Turing, ¿Qué incluye?x. Q: Conjunto finito de estados. b: Símbolo que representa el espacio vacío. Γ: Alfabeto de símbolos en la cinta. F: Conjunto de estados finales o de aceptación. q1: Estado inicial.

Un compilador debe realizar las siguientes Tareas: Selecciona 4 (cuatro) respuestas correctas. Análisis Léxico. Análisis Semántico. Análisis Sintáctico. Generación de código objeto. Lectura.

¿Cuál de los siguientes autómatas puede reconocer el lenguaje L = {wcwR| w en (a+b)*} donde R = reverso ?. AP. ALA. MT.