Lenguajes Formales y Computabilidad

La unión de un número arbitrario finito de alfabetos da como resultado: Un alfabeto válido. Un alfabeto infinito. Un alfabeto finito. Un alfabeto arbitrario.

Para diseñar un sistema de control es necesario crear una gramárica tal que el lenguaje generado consiste en palabras con un conjunto de 1s seguido de un conjunto de 0s, con la condición que la cantidad de 1 sea impar y la cantidad de cero sea par. ¿Cuál es la gramárica necesaria asumiendo que el axioma es Exp?. (Exp:= unos ceros), (Ceros:= ceros 00 | 00), (Unos:= unos 11 | 1). (Exp:= unos ceros), (Ceros:= ceros 00 | 00), (Unos:= unos 11 | 11). (Exp:= unos ceros), (Ceros:= ceros 00 | 0), (Unos:= unos 11 | 11). (Exp:= unos ceros), (Ceros:= ceros 00 | 0), (Unos:= unos 11 | 1).

Dado el autómata siguiente, representado por la tabla de transición, ¿Cual o cuales de los estados pueden eliminarse por ser "no conexos"?. Los estados Q2 y Q4 no son accesibles desde el estado inicial Q0, por lo tanto pueden eliminarse sin causar modificaciones al autómata finito. Los estados Q2 y Q4 son accesibles desde el estado inicial Q0, por lo tanto pueden eliminarse sin causar modificaciones al autómata finito. Los estados Q4 y Q5 son accesibles desde el estado inicial Q0, por lo tanto pueden eliminarse sin causar modificaciones al autómata finito. Los estados Q4 y Q5 no son accesibles desde el estado inicial Q0, por lo tanto pueden eliminarse sin causar modificaciones al autómata finito.

El número mínimo de estados de un autómata finito determinista es: Uno. Depende del alfabeto de los símbolos de entrada. Depende del alfabeto de los símbolos de salida. Cero.

Sea el alfabeto Σ={1, 2, 3} ¿Cuál de las cadenas pertenece a L(Σ)?. c= 312. c=3421. c=336. c=114.

Una máquina de Mealy es una máquina secuencial en la que la salida se produce: Durante la transición. Antes de la transición. Después de la transición. En cada estado.

El autómata cuyo diagrama de estados se muestra en la imágen acepta cadenas formadas por una secuencia de letras "a" de cualquier longitud, incluso nula. Verdadero. Falso.

Una máquina de Mealy es una máquina secuencial en la que la salida depende de: Del estado actual y del estado inicial de la máquina. Del símbolo de entrada y del estado actual de la máquina. Del símbolo de entrada y del estado anterior de la máquina. Del símbolo de entrada y del estado de la máquina.

Una máquina de Mealy es: Una máquina secuencial que genera salidas. Una máquina secuencial que no genera salidas. Una máquina secuencial que genera transiciones.

En un autómata finito determinista (AFD) un estado se dice "no conexo" si: No puede ser alcanzado desde el estado inicial, independientemente de la cadena de entrada. Puede ser alcanzado desde el estado inicial, independientemente de la cadena de entrada. Puede ser alcanzado desde el estado inicial, dependiendo de la cadena de entrada.

Suponiendo el autómata identificado por su diagrama de estados en la siguiente imagen, determine las cadenas aceptadas por el mismo: Cadenas que inician con uno y terminan con cero o uno. Cadenas que contienen al menos dos ceros consecutivos.

La función de transición de estados de la maquina de Mealy se define como: QxΣe→Q. QxΣe→λ. Qxλ→Σe.

Sean A y B conjuntos, la intersección de A y B (denotada A∩B) es un conjunto que cumple con: Ser el conjunto formado por los elementos comunes entre A y B. Ser el conjunto formado por todos los elementos que están en A o en B. Ser el conjunto formado por los elementos resultantes entre A - B. Ser el conjunto formado por los elementos no comunes entre A y B.

¿Para qué se utilizan los autómatas finitos generalmente? Seleccione las dos (2) opciones correctas: Para verificar que las cadenas pertenecen al lenguaje. Para reconocer cadenas de todo tipo de lenguajes. Como un analizador durante una parte del proceso de compilación de un lenguaje de alto nivel. Para verificar que las cadenas pertenecen a un lenguaje ambiguo.

La unión de un número arbitrario finito de alfabetos da como resultado: Un alfabeto válido. Un alfabeto infinito. Un alfabeto idéntico al que tiene un número mayor de símbolos. Un alfabeto infinito.

Suponiendo la gramática G=({0,1},{A,B}), A, P), donde P={(A:=1B1),(A:=11),(B:=1),(B:=0)}. Es posible decir que G es: Una gramática Independiente del contexto (tipo 2). Una gramática Dependiente del contexto (tipo 1). Una gramática Regular (tipo 3).

Un autómata finito determinista puede tener solamente un estado de aceptación. Verdadero. Falso.

Con respecto a las expresiones regulares, ¿Cuales de las siguientes afirmaciones son correctas? Seleccionar las tres (3) opciones correctas. Si a es una expresión regular, (a) es una expresión regular. Si a es una expresión regular, a* es una expresión regular. Si a es una expresión regular a.b es una expresión regular aun si b no es regular. para cada a que pertenece a Σ, a es una expresión regular.

Dados dos lenguajes L1 sobre el alfabeto Σ1 y L2 sobre el alfabeto Σ2, la concatenación de L1 con L2 (L1.L2) se define como: L1.L2=(y.x / y∈L2, x∈L1). L1.L2=(x.y / x∈L1, y∈L2).

Dos gramáticas son equivalentes si: Generan el mismo lenguaje. Generan la misma gramática. Generan el mismo alfabeto.

Una gramática es recursiva si: Tiene al menos una producción recursiva. Tiene producciones recursivas tanto por derecha como por izquierda.

Con respecto al lenguaje reconocido, es posible afirmar que: Los autómatas finitos son capaces de reconocer palabras pertenecientes a cualquier tipo de lenguaje. Los autómatas finitos son capaces de reconocer solamente cadenas pertenecientes a lenguajes generados por gramáticas de tipo 3. Los autómatas finitos son capaces de reconocer solamente cadenas pertenecientes a lenguajes generados por gramáticas de tipo 2.

Dado el siguiente diagrama de estados que representa un autómata finito es posible afirmar que: Se trata de un autómata finito determinista que acepta cadenas que inician con cero y termina con uno. Se trata de un autómata finito no determinista que acepta la cadena vacía o cadenas que inician con cero, terminan con uno y no tienen símbolos iguales consecutivos. Se trata de un autómata finito no determinista que acepta la cadena vacía o cadenas que inician con cero, terminan con uno y tienen símbolos iguales consecutivos. Se trata de un autómata finito determinista que acepta la cadena vacía o cadenas que inician con cero, terminan con uno y no tienen símbolos iguales consecutivos.

Si E1 y E2 son expresiones regulares, ¿Cuáles de las siguientes expresiones también lo son? Seleccione las cuatro (4) opciones correctas. E1|E2. E. E1*. E1.E2. (E1).

Un sistema de numeración está definido por un conjunto de símbolos que pueden concatenarse de modo de representar cantidades. La base del sistemas de numeración coincide con la cantidad de símbolos diferentes del sistemas. El sistema puede ser definido mediante una gramática formal que difiere según la base del mismo. Si el sistema a definir es el sistema binario, ¿Cuál de las siguientes gramáticas generaría las cadenas correctas?. ΣNT={digito, otrodigito, otrodigito, base2, vacio} ΣT={0,1} P={(base2:= digito otrodigito), (otrodigito:=digito otrodigito, otrodigito), (otrodigito:= vacio), (digito:=0/1), (vacio:=)}. ΣNT={digito, otrodigito, base2, vacio} ΣT={0,1} S= base2 P={(base2:= digito otrodigito), (otrodigito:=digito otrodigito), (otrodigito:= vacio), (digito:=0/1), (vacio:=)}.

Una gramática es ambigua si: Si es una gramática recursiva. Tiene al menos una sentencia ambigua. Si es una gramática regular derecha.

Suponiendo un autómata finito con la siguiente tabla de transición: estado 0 1 -> s0* s1 s0s1 s1 s1. ¿Que clase de palabras son aceptadas por el autómata?. Cadenas formadas por secuencias de ceros y unos alternados de al menos dos símbolos. Cadenas formadas por secuencias de unos de cualquier longitud, incluyendo la cadena vacia. Cadenas formadas por secuencias de ceros de cualquier longitud, incluyendo la cadena vacia. Cadenas formadas por secuencias de ceros y unos alternados de al menos 1 símbolo.

Seleccione las tres (3) respuestas correctas: Por definición una gramática es una cuádrupla cuya expresión formal es G:{Σt, Σnt, S, P}. Con base en esta definición indique cuáles de las siguientes afirmaciones son correctas: Σt= alfabeto de los símbolos terminales, Σnt= alfabeto de los símbolos no terminales, S= es un símbolo terminal particular llamado synthograma y P es el conjunto de producciones exclusivas. Σt= alfabeto de los símbolos terminales, Σnt= alfabeto de los símbolos no terminales, S= es un símbolo no terminal particular llamado axioma y P es el conjunto de producciones. Σt= alfabeto de los símbolos terminales, Σnt= alfabeto de los símbolos no terminales, S= es un símbolo no terminal y P un conjunto de reglas. Σt= alfabeto de los símbolos terminales, Σnt= alfabeto de los símbolos no terminales, S= es el axioma y P las reglas de derivación.

Dado un lenguaje L1 sobre el alfabeto Σ1 la potencia i-esima de L1 se define como: Potencia i-esima de L1 = {}. Potencia i-esima de L1 = {L1.L1.L1. ... . L1}.

Un autómata finito determinista: Tiene transiciones espontáneas y puede estar en mas de un estado a la vez. Carece de transiciones espontáneas y está imposibilitado de estar en mas de un estado a la vez.

Seleccione las tres (3) opciones correctas: Un autómata finito se dice no determinista si: Para un mismo par (estado, entrada) hay mas de una transición posible. Existen una o mas transiciones no definidas. Posee transiciones espontáneas entre estados. Carece de transiciones espontáneas entre estados. No existen transiciones no definidas.

Seleccione las cuatro (4) opciones correctas: El diagrama de estados o diagrama de transiciones es un g............... donde: Los nodos representan los posibles estados del autómata. Los estados finales se identifican como nodos con círculo doble. Las transiciones se identifican mediante un arco que parte de un nodo, llega a otro y se halla rotulado con un elemento perteneciente al alfabeto de los símbolos de entrada. El estado inicial se identifica con un arco entrante no rotulado. El estado inicial se identifica con un arco entrante rotulado.

Dado el siguiente autómata finito AFD=({0,1},{q0, q1,q2, q3, q4}, q0, f, {q2}) cuya función de transición está definida por: f(q0,0)=q0, f(q0,1)=q4, f(q1,0=q1), f(q1,1)=q2, f(q2,0)=q2, f(q2,1)=q2, f(q3,0)=q3, f(q3,1)=q2, f(q4,0)q0, f(q4,1)=q2 ¿Cuál o cuáles de los estados del autómata son estados no conexos?. Los estados no conexos son Q1 y Q3. Los estados no conexos son Q4 y Q3. Los estados no conexos son Q2 y Q3.