LENGUAJES FORMALES Y COMPUTABILIDAD (Simulacion del segundo Parcial)

En la construcción de un autómata a pila a partir de una gramática en forma normal de Greibach, ¿qué se coloca inicialmente en la pila?. El axioma de la gramática. La cadena λ. El símbolo de fondo # únicamente. Todos los terminales del alfabeto. El primer símbolo de entrada.

¿Cuál es el orden correcto de prioridad de los operadores en expresiones regulares?. Primero +, luego. , y finalmente∗. Primero ∗, luego ⋅, y finalmente +. Primero ⋅, luego ∗, y finalmente +. Todos los operadores tienen la misma prioridad. La prioridad depende del alfabeto considerado.

¿Qué información contiene una descripción instantánea de un autómata a pila?. El lenguaje aceptado hasta el momento. El estado actual, la entrada restante y el contenido de la pila. El conjunto de estados finales y la función de transición. El estado inicial, el alfabeto de entrada y el símbolo de fondo. El historial completo de transiciones realizadas.

¿Qué relación formal se establece entre los autómatas a pila y las gramáticas independientes del contexto?. Reconocen y generan exactamente la misma clase de lenguajes. Las gramáticas tipo 2 generan únicamente lenguajes regulares. No existe una correspondencia formal entre ambos modelos. Los autómatas a pila son equivalentes a las gramáticas tipo 1. Los autómatas a pila reconocen un subconjunto propio de los lenguajes generados por gramáticas tipo 2.

Se dispone de una M aquina de Turing M que acepta un lenguaje L. Para una palabra w, se observa que M nunca se detiene al ejecutars con w. ¿Que conclusion es necesariamente correcta?. w∉/L y L podria ser recursivamente enumerable. No puede extraerse ninguna conclusión sobre w. w∈L y L es decidible. w∈L y L es recursivamente enumerable. w∉/L y L es recursivo.

¿Cuál es la forma general de las ecuaciones características utilizadas en el análisis de un autómata finito?. X=A∪B. X=A*+B*. X=A⋅X+B. X=A+X⋅B. X=λ.

Seleccione las 3 (tres) opciones correctas en relación al método empírico de construcción de autómatas a partir de expresiones regulares. El autómata resultante es siempre determinista y mínimo. El lenguaje reconocido por el autómata construido coincide con el lenguaje de la expresión regular. El autómata obtenido a partir de una expresión regular es necesariamente no determinista. El método empírico ER→AF construye un autómata con transiciones espontáneas. El método empírico evita completamente el uso de transiciones λ.

¿Cuál es el significado del símbolo λ en una expresión regular?. La cadena vacía. Una concatenación indefinida de símbolos. Una cadena de longitud uno. Un símbolo cualquiera del alfabeto. El conjunto vacío.

En el metodo de analisis de un automata finito, ¿que representa la variable xi asociada a un estado qi?. El conjunto de estados alcanzables desde qi. La función de transición saliente de qi. El conjunto de cadenas que llevan desde qi hasta algún estado final. El conjunto de símbolos del alfabeto reconocidos en qi. La expresión regular mínima del autómata completo.

¿Cuál es la función del símbolo blanco b en una Máquina de Turing?. Representar el final de la computación. Separar símbolos del alfabeto de entrada. Marcar el inicio de la entrada. Identificar el estado inicial. Indicar las celdas vacías de la cinta.

Seleccione las 4 (cuatro) opciones correctas en relación al proceso de eliminación de estados y la construcción de expresiones regulares. Caminos alternativos entre dos estados se representan mediante la unión de expresiones regulares. Al eliminar un estado con un bucle, el rótulo del bucle se traduce mediante una clausura de Kleene. Pasar por un estado intermedio se modela mediante la concatenación de expresiones regulares. La eliminación de estados produce directamente un autómata determinista mínimo. El proceso puede generar expresiones regulares intermedias más complejas que la final.

Se tiene una producción de una gramática en forma normal de Greibach A::=aBC. ¿Qué transición corresponde en el autómata a pila construido a partir de esta gramática?. Consumir BC y apilar a. Reemplazar A por a sin consumir entrada. Consumir a y apilar A sobre BC. Consumir a y reemplazar A en el tope de la pila por BC. No consumir entrada y reemplazar BC por A.

¿Qué afirma el teorema de análisis en relación con los lenguajes aceptados por autómatas finitos?. Que los lenguajes aceptados por autómatas finitos son siempre infinitos. Que todo lenguaje aceptado por un autómata finito es regular. Que solo los autómatas deterministas aceptan lenguajes regulares. Que todo lenguaje regular es aceptado por un autómata a pila. Que todo autómata finito acepta un único lenguaje.

El método empírico de eliminación de estados garantiza que la expresión regular obtenida sea siempre única. Verdadero. Falso.

¿Cuál es el objetivo principal de transformar una gramática tipo 2 a la forma normal de Greibach antes de construir un autómata a pila?. Facilitar la simulación directa de derivaciones mediante la pila. Garantizar que el lenguaje generado sea regular. Asegurar que el autómata resultante sea determinista. Evitar completamente las transiciones espontáneas. Eliminar la necesidad de símbolos no terminales.

Seleccione las 2 (dos) opciones correctas en relación al comportamiento de los procedimientos de reconocimiento en lenguajes recursivamente enumerables. En un lenguaje recursivamente enumerable, la máquina siempre se detiene en estado no final cuando w∉/L. En un lenguaje recursivamente enumerable, si w∈L existe un procedimiento que acepta w. En un lenguaje recursivamente enumerable, si w∉/L el procedimiento puede no detenerse. Los lenguajes recursivamente enumerables son un subconjunto propio de los lenguajes recursivos. Todo lenguaje recursivamente enumerable es aceptado por un autómata finito.

¿Cuál es la definición formal de la función de transición de un autómata a pila?. Q×Γ→Q×Γ. Q×Σₑ→Q. Σₑ×Γ→Q. Q×Σₑ×Γ→Q×Γ. Q×Σₑ→Γ.

¿Qué característica define a una gramática bien formada?. Todas sus producciones están en forma A::=a. Se encuentra necesariamente en forma normal de Chomsky. No contiene símbolos inaccesibles ni símbolos superfluos. Genera únicamente lenguajes finitos. Posee un único no terminal.

¿Cuál es el tipo de autómata que se obtiene, en general, al convertir una gramática regular por derecha?. Un autómata finito no determinista. Un autómata finito determinista. Un autómata lineal acotado. Un autómata a pila determinista. Una máquina de Turing.

¿Cuál es el propósito del símbolo # en un autómata a pila?. Codificar el alfabeto de entrada. Identificar el estado inicial. Señalar una transición espontánea. Representar el símbolo vacío de entrada. Marcar el fondo de la pila.