Lenguajes Formales y Computabilidad (2do Parcial)

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 válidas sobre la pila? 4 opciones correctas. 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. .......

¿Cuál es la expresión regular que denota el lenguaje de todas las cadenas sobre el alfabeto {a,b} que contienen la cadena ba?. ..... (a+b)ba(a+b).

Si la entrada de la máquina, cuyo diagrama de estados se muestra en la siguiente imagen, es 1010, ¿Cuál será la cadena resultante de la operación de la máquina?. ... 10100ʼ.

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. .......

¿Cuál de las siguientes afirmaciones es verdadera en relación a los lenguajes aceptados por los autómatas finitos?. ........ Los lenguajes aceptados por los autómatas finitos son fácilmente descritos por expresiones simples llamadas expresiones regulares.

Un proceso que puede resolverse mediante una máquina de Turing se conoce como: Proceso computable. ...........

Dado un autómata finito determinista AFD={∑, Q, f, q0, F} es posible obtener la gramática G=(∑N, ∑T, S, P), donde ∑N, alfabeto de los ¨no terminales¨, se obtiene a partir de: El conjunto Q de estados del autómata finito. .........

¿Cuál es la expresión regular que denota el lenguaje de todas las cadenas sobre el alfabeto {a,b} que comienzan con b?. ................................ b(a+b)*.

Si en un autómata finito, q0 es el estado inicial, ¿Qué se obtiene resolviendo su ecuación característica x0?. .............. El lenguaje regular aceptado por el autómata finito.

Dada la expresión formal de una gramática regular G=(∑N, ∑T, S,P) es posible obtener el autómata finito AFD={∑, Q, f, q0, F} que reconoce el lenguaje generado por ella, donde Q, el conjunto de estados del autómata, se obtiene a partir de: El alfabeto de los símbolos no terminales. .............

¿Cuál es el lenguaje aceptado por el autómata a pila cuyo diagrama de estados se muestra en la siguiente imagen?. .......... L={aⁿ bⁿ con n>=0}.

En el diagrama de estados de una máquina de Turing, los arcos que representan las transiciones se encuentran etiquetadas con: .................. El símbolo que se lee en la cinta, el símbolo que se escribe en la cinta y el movimiento que realiza el cabezal.

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

¿Cuál es el cálculo que realiza la máquina de Turing que se muestra en la siguiente imagen?. Calcula el doble de un número expresado en binario. .....

¿Cuál de las siguientes opciones es un metalenguaje para expresar el conjunto de palabras aceptadas por un autómata finito?. Una expresión regular. .........

Suponiendo la gramática regular G=({0,1},{A, B, C}, A, P) P={ (A:=0B), (A:=λ), (B:=1C), (B:=1), (C:=0B) }. El conjunto de estados del autómata obtenido a partir de ella es: .................................... Q={A, B, C, F}.

¿Cuáles de las siguientes opciones se relacionan con características de una máquina de Turing? 3 opciones correctas. Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal de datos. En cada instante la máquina puede leer un sólo dato de la secuencia. El cabezal puede moverse a derecha (R) a izquierda (L) y leer el contenido de una celda o escribir en ella. .........

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

¿Cuáles de las siguientes afirmaciones son correctas en relación a la máquina de Turing universal? 4 opciones correctas. La información de entrada es una cadena que el cabezal lee desde la cinta. ................................. Se comporta como un ordenador, ya que puede cargarse tanto el programa como los datos. Es una máquina de Turing que puede simular cualquier otra máquina de Turing. La tabla de acciones de la máquina se codifica en una cadena que se lee desde la cinta.

¿Cuál de las siguientes afirmaciones son correctas como definición de equivalencia entre dos máquinas de Turing? 4 opciones correctas. Dos máquinas de Turing son equivalentes si ambas realizan la misma acción sobre todas sus entradas. Dos máquinas de Turing son equivalentes si una no para para alguna entrada, la otra tampoco lo hace. Dos máquinas de Turing son equivalentes si ambas aceptan y/o reconocen las mismas palabras. Dos máquinas de Turing son equivalentes si para cada entrada posible, los contenidos de la cinta al final del proceso son iguales. ...................