Simulador 2do Parcial Lenguajes Formalea y Computabilidad

(ab+ab*a) *. (ababa) *. a* (ababa) *. (ab+ab*a) *b. b* (ababa)*.

(ab)*. a+b. a*. b*. (ab)*a.

Los lenguajes aceptados por los autómatas finitos son fácilmente descritos por expresiones complejas llamadas expresiones compuestas. Verdadero. Falso.

f: Q × Σ → Q × Γ × (I, D, P). f: Q × Γ → Q × Γ × Σ. f: Q × Γ → Q × Γ × (I, D, P). f: Q × Γ → P × Γ × (I, D, P). f: Q × Σ → Q × Σ × (I, D, P).

El símbolo ∅ (conjunto vacío) es una expresión regular. 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. Los símbolos (A.B) son expresiones irregulares siempre que A y B sean expresiones regulares. El símbolo λ (conjunto {λ}) es una expresión regular.

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 posee una cinta de longitud finita. No es posible una máquina de Turing para simular el comportamiento de una computadora. Un problema que puede resolverse mediante una computadora no necesariamente puede resolverse con una máquina de Turing. 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.

Dos casos bases que la determinan. Un conjunto de casos recursivos que las definen. Tres casos base que las definen. Un conjunto de casos base y un conjunto de casos recursivos. No existe una definición general para las expresiones regulares.

El conjunto de estados. El alfabeto de símbolos en la cinta. El conjunto de estados de salida. El alfabeto de símbolos de entrada. El conjunto de símbolos de salida.

Expresiones regulares complementarias. Autómatas regulares. Expresiones regulares equivalentes. Expresiones irregulares equivalentes. Autómatas de pila.

La clausura o clausura de Kleene se representa con: No hay representación. Un #. El símbolo Σ. Un asterisco (*). Un +.

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

Un arco del diagrama de un autómata a pila, que conecta los estados p y q está etiquetado con a,##a, significa que: El autómata realiza una modificación desde el estado p con una entrada a y la pila repleta y llega al estado q apilando el símbolo a. El autómata realiza una transición desde el estado p con una entrada vacía y el tope de pila en a y llega al estado q apilando otro símbolo a. El autómata realiza una transición desde el estado p con una entrada a y la pila vacía y llega al estado q apilando el símbolo a. El autómata realiza una transición desde el estado q con una entrada a y la pila vacía y llega al estado p desapilando el símbolo a. El autómata realiza una transición desde el estado q con una entrada a y el tope en a y llega al estado p apilando el símbolo a.

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

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

Suponiendo que es necesario reconocer las cadenas del lenguaje formado por las cadenas sobre el alfabeto {0,1} que tienen igual cantidad 1´s y 0´s. ¿Qué tipo de autómata se debería usar?. Un autómata finito, ya que el lenguaje es regular. Un autómata a pila, ya que el lenguaje es independiente del contexto. Una máquina de Turing, ya que es un lenguaje regular. Un autómata finito determinista, ya que el lenguaje es regular y ambiguo. Un autómata infinito.

Un lenguaje se dice inherentemente ambiguo si: No es posible decir cuando un lenguaje es inherentemente ambiguo. No existe una gramática no ambigua que lo genere. Si existe como mínimo una gramática ambigua que lo genera. Si existe una gramática lineal. Si existe una gramática ambigua que lo genera.

¿Cuál es el tipo de autómata capaz de reconocer el lenguaje L= {x^n y^m | n > 1}?. Un autómata finito determinista. Un autómata infinito. Una máquina de Turing. Un autómata finito no determinista. Un autómata a pila.

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 f se calcula según lo siguiente: Si A := aB entonces f(B,a) = A, si A := a entonces f(A, λ) = F, si S := λ entonces f(S, a) = F. Si A := aB entonces f(A,a) = B, si A := a entonces f(A, λ) = F, si S := λ entonces f(S, a) = F. Si A := aB entonces f(B,a) = A, si A := a entonces f(A,a) = F, si S := λ entonces f(S, λ) = F. Si A := aB entonces f(A,a) = B, si A := a entonces f(A,a) = F, si S := λ entonces f(S, λ) = F. Si A := aB entonces f(A,b) = B, si A := a entonces f(A,a) = F, si S := λ entonces f(S, λ) = F.

La función de transición de estados del autómata finito. El conjunto Q de estados del autómata finito. El conjunto de estados de salida. El conjunto de estados intermedios. El alfabeto de los símbolos de entrada.

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

Toda máquina de Turing posee: Una cinta infinita dividida en celdas y un cabezal de lectura/escritura que puede moverse en ambas direcciones sobre ella. Una cinta finita multiplicada en celdas y un cabezal de lectura/escritura que puede moverse en ambas direcciones sobre ella. Una cinta infinita dividida en celdas y un cabezal de lectura/escritura que puede avanzar sobre ella. Una cinta infinita dividida en celdas y un cabezal de lectura que puede moverse en ambas direcciones sobre ella. Una cinta finita dividida en celdas y un cabezal de lectura/escritura que puede moverse en ambas direcciones sobre ella.

Transforma la cadena de entrada reemplazando la subcadena "ab" por "aa". Transforma la cadena de entrada reemplazando la subcadena "ab" por "ba". Transforma la cadena de entrada reemplazando la subcadena "ba" por "ab". Transforma la cadena de entrada reemplazando la subcadena "aa" por "bb". Transforma la cadena de entrada reemplazando la subcadena "bb" por "aa".

A diferencia de los autómatas finitos, los autómatas a pila cuentan con: Más de un alfabeto de entrada. Una memoria flexible. Mayor número de estados. Una memoria auxiliar. Menor número de estados.

Sea un autómata a pila AP y una cadena x ∈ L [AP]. Si el autómata lee la cadena x, ¿llegará necesariamente a un estado de aceptación?. No, nunca llegará a un estado de aceptación. Sólo algunas veces. No es posible saber si llegará a un estado de aceptación o no. Sí, siempre llegará a un estado de aceptación. Nunca, queda en un bucle, ya que sólo lee un símbolo.

Las expresiones regulares se definen mediante: Un conjunto de casos recursivos que las definen. Un conjunto de casos base y un conjunto de casos recursivos. Dos casos base que las determinan. Tres casos base que las definen. No existe una definición general para las expresiones regulares.

Si existe como mínimo una gramática ambigua que lo genera. Si existe una gramática lineal. Si existe una gramática ambigua que lo genera. No es posible decir cuando un lenguaje es inherentemente ambiguo. No existe una gramática no ambigua que lo genere.

El axioma S de la gramática regular. El axioma C de la gramática regular. El conjunto de producciones de la gramática. El alfabeto de los símbolos terminales. El alfabeto de los símbolos no terminales.

Seleccione las 4 (cuatro) opciones correctas. ¿Cuáles de las siguientes afirmaciones son correctas como definición de equivalencia entre dos máquinas de Turing?. Dos máquinas de Turing realizan la misma acción sobre sus entradas, sin embargo, nunca son equivalentes. Dos máquinas de Turing son equivalentes si para cada entrada posible, los contenidos de la cinta al final del proceso son iguales. 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 realizan la misma acción sobre todas sus entradas. Dos máquinas de Turing son equivalentes si ambas aceptan y/o reconocen las mismas palabras.

El alfabeto de entrada es idéntico al alfabeto de símbolos en la cinta. Realiza una transición espontánea desde el estado final. Modifica el contenido de la cinta realizando cierta función. Reconoce o acepta un lenguaje L. Realiza una transición espontánea desde el estado inicial.

Σ = {0, 1, B} donde B identifica el blanco. Σ = {1, 1, #}. Σ = {0, 1}. Σ = {0, 1, #}. Σ = {0, 1, #, B}.

a(aa + b). (aa + b)*. a(ab + b). a(a + b)*. a(aa + b)*.

En la transición entre q0 y q1 con una entrada λ y tope de la pila en a, se apila X. En la transición entre q0 y q1 con una entrada a y tope de la pila en λ, se apila X. En la distancia entre q0 y q1 con una salida λ y tope de la pila en a, se apila X. En la transición entre q1 y q0 con una entrada a y tope de la pila en λ, se apila X. En la transición entre q0 y q1 con una entrada a y tope de la pila en X, ese tope se desapila.

Calcula el antecesor de un número en notación unaria. Calcula el sucesor de un número en notación binaria. Calcula el antecesor de un número en notación binaria. Calcula el sucesor de dos número en notación binaria. Calcula el sucesor de un número en notación unaria.

C0:=0C1/1C2/1 C1:=0C1/1C3 C2:=0C0/1C4 C3:=0C3/1C3 C4:=0C0/1C4/0. C0:=0C1/1C2 C1:=0C1/1C3 C2:=0C0/1C4/1 C3:=0C3/1C3 C4:=0C0/1C4/1. C0:=0C1/1C2/1 C1:=0C1/1C3 C2:=0C0/1C4/1 C3:=0C3/1C3 C4:=0C0/1C4/1. C0:=0C1/1C2 C1:=0C1/1C3 C2:=0C0/1C4 C3:=0C3/1C3 C4:=0C0/1C4. C0:=0C1/1C2/1 C1:=0C1/1C3 C2:=0C0/1C4 C3:=0C3/1C3 C4:=0C0/1C4.

Lenguaje aceptado por estado inicial. Lenguaje aceptado por entrada vacía. Lenguaje no aceptado por estado inicial. Lenguaje aceptado por vaciado de pila. Lenguaje aceptado por estado final.

wxy. wx*y. wx+y. wxy+. w*xy.

Es reconocida por un autómata de pila. Es reconocida por un autómata de estado no finito. Es reconocida por un autómata de estado finito. Es reconocida por una máquina de Moore. Es reconocida por un autómata infinito.

Seleccione las 4 (cuatro) opciones correctas. ¿Cuáles de las siguientes afirmaciones se relacionan con las máquinas de Turing y los lenguajes reconocidos?. Una máquina de Turing reconoce lenguajes de tipo 3. Los lenguajes de tipo 0 describen todo problema que puede ser resuelto por una computadora. Todo procedimiento computacional puede ser realizado por una máquina de Turing. Si un problema no puede ser resuelto con una máquina de Turing entonces no tiene solución computacional. Una máquina de Turing reconoce lenguajes de tipo 0.

El conjunto de estados intermedios. El conjunto Q de estados del autómata finito. La función de transición de estados del autómata finito. El alfabeto de los símbolos de entrada. El conjunto de estados de salida.

Verdadero. Falso.

Verdadero. Falso.

Un lenguaje regular puede ser aceptado por un autómata finito. Todo lenguaje aceptado por un autómata finito es regular. Todo lenguaje regular es aceptado por un autómata finito. Uno de los lenguajes que puede aceptar un autómata finito es el regular. Uno de los lenguajes está incluido en el otro.

Autómata específico. Autómata finito. Autómata irregular. Autómata infinito. Autómata especial.