LENGUAJES FORMALES Y COMPUTABILIDAD (simulacion primer Parcial)

Seleccione las 3 (tres) opciones correctas en relación al cierre-· 𝜆 λ· y su uso en autómatas finitos no deterministas. El cierre- λ elimina estados finales. El cierre- λ de un estado incluye a todos los estados alcanzables mediante transiciones . λ. El cierre- λ se usa en la conversión de AFND a AFD. El cierre- λ reduce el alfabeto de entrada. El cierre- λ es una relación reflexiva.

¿Cuál es la única restricción que debe cumplir una producción en una gramática de tipo 0?. El miembro derecho no puede ser vacío. El miembro izquierdo debe ser un único no terminal. El miembro izquierdo debe contener al menos un símbolo no terminal. La producción debe depender del contexto. El miembro derecho debe contener solo terminales.

¿Cuál de las siguientes afirmaciones es correcta para todo autómata finito determinista?. Puede carecer de función de transición para algún símbolo de Σ. Acepta palabras solo si termina en q0. Reconoce lenguajes libres de contexto no regulares. Para cada par (q,a)∈Q×Σ existe una única transición definida. Puede tener más de un estado inicial.

Sea Σ={a,b} y sea w=abba. ¿Cual de las siguientes expresiones es correcta?. w∈Σ. ∣w∣=∣Σ∣. w^2=abba. w^−1=baab. ∣w∣=4.

Seleccione las 4 (cuatro) opciones correctas en relación a las gramáticas regulares y sus producciones. Las gramáticas regulares permiten producciones con dos símbolos no terminales en el lado derecho. En cada producción de una gramática regular, el lado derecho contiene un símbolo terminal y a lo sumo un no terminal. Las gramáticas regulares pueden ser lineales por derecha o por izquierda. Las gramáticas regulares generan lenguajes reconocidos por autómatas finitos. Las gramáticas regulares son las más restrictivas de la jerarquía de Chomsky.

En el método de subconjuntos para convertir un AFND en un AFD, ¿qué representan los estados del AFD resultante?. Subconjuntos de Q. Clases de equivalencia de Myhill–Nerode. Estados individuales del AFND. Símbolos del alfabeto Σ. Estados finales únicamente.

¿Cuál es el criterio principal para clasificar las gramáticas en la jerarquía de Chomsky?. El número de derivaciones posibles. El lenguaje específico que generan. La cantidad de símbolos no terminales. El tamaño del alfabeto terminal. La forma de las producciones.

¿Cuál de las siguientes afirmaciones es correcta sobre una máquina de Mealy?. La salida depende solo de la entrada recibida. No utiliza función de salida. No posee función de transición. La salida depende únicamente del estado presente. La salida depende del estado presente y de la entrada recibida.

¿Cuál es el criterio principal para clasificar las gramáticas en la jerarquía de Chomsky?¡. El número de derivaciones posibles. El lenguaje específico que generan. La cantidad de símbolos no terminales. El tamaño del alfabeto terminal. La forma de las producciones.

Seleccione las 4 (cuatro) opciones correctas en relación a las características de los autómatas finitos no deterministas (AFND). El lenguaje aceptado por un AFND se define por intersección no vacía con F. Un AFND puede tener transiciones espontáneas etiquetadas con λ. En un AFND puede no existir transición definida para algún par (q,a). En un AFND la función de transición puede devolver un conjunto de estados. En un AFND toda transición debe estar definida para cada símbolo de Σ.

¿Cuál de las siguientes opciones define correctamente una sentencia de una gramática?. Cualquier cadena que contenga al menos un símbolo no terminal. Una producción de la forma α→β. Una cadena que pertenece a ΣN. Una forma sentencial compuesta solo por símbolos terminales. El símbolo inicial de la gramática.

Todo AFND puede convertirse en un AFD equivalente que reconozca el mismo lenguaje. Verdadero. Falso.

¿Qué representa el conjunto F en un autómata finito determinista?. El alfabeto de entrada. El conjunto de estados iniciales. La función de transición. El conjunto de palabras aceptadas. El conjunto de estados de aceptación.

¿Cuál de las siguientes afirmaciones es correcta sobre el AFD mínimo equivalente a un AFD dado?. Solo se obtiene eliminando estados no accesibles. Depende del orden en que se agrupan los estados. Puede tener más estados que el autómata original. No siempre existe. Es único salvo isomorfismo.

¿Cuál de las siguientes afirmaciones es correcta sobre la conversión de un AFND a un AFD?. El AFD obtenido siempre tiene menos estados que el AFND. El AFD obtenido elimina la necesidad de la función de transición. El AFD obtenido reconoce un lenguaje distinto. El AFD obtenido no necesariamente es mínimo. El AFD obtenido no puede tener estados finales.

Seleccione las 4 (cuatro) opciones correctas en relación a la función de transición y el reconocimiento de lenguajes en un AFND. La función de transición de un AFND tiene codominio P(Q). Un AFND reconoce lenguajes regulares. Un AFND puede aceptar una palabra si existe al menos un recorrido aceptante. Todo AFND es determinista por definición. En un AFND el dominio de f incluye Σ∪λ.

¿Cuándo se dice que una gramática es ambigua?. Cuando genera un lenguaje finito. Cuando posee producciones recursivas. Cuando contiene más de un símbolo inicial. Cuando todas sus sentencias tienen una única derivación. Cuando existe al menos una sentencia con más de un árbol de derivación.

Sea un AFD A=(Σ,Q,f,q0,F) y sea q∈Q un estado no accesible desde q0. ¿Cual de las siguientes afirmaciones es correcta?. Eliminar q altera necesariamente el conjunto F. Eliminar q hace que el autómata deje de reconocer un lenguaje regular. Eliminar q no modifica el lenguaje reconocido por A. Eliminar q impide definir la funcion f. Eliminar q impide que el automata sea determinista.

¿Cuál es la diferencia fundamental entre una máquina de Mealy y una máquina de Moore?. Solo la máquina de Mealy posee estados finales. En Mealy la salida depende de la transición, mientras que en Moore depende del estado. Ambas definen la salida de la misma manera. En Moore la salida depende de la transición, mientras que en Mealy depende del estado. Solo la máquina de Moore tiene función de transición.

Una expresión regular puede describir exactamente el mismo lenguaje que una gramática regular. Verdadero. Falso.

Sea Σ={a,b}. ¿Que lenguaje denota la expresion regular (a+b)b^∗?. El conjunto de todas las cadenas formadas solo por b, incluyendo la cadena vacıa. El conjunto vacío. El conjunto de todas las cadenas que comienzan con a o b seguidas de cero o mas b. El conjunto de todas las cadenas que terminan en a. El conjunto de todas las cadenas que contienen al menos una a.