Lenguajes Formales y Computabilidad

Sean A y B conjuntos, la interseccion de A y B (denotada A n B) es un conjunto que cumple con: Ser el conjunto formado por todos los elementos que estan en A o en B. Ser el conjunto formado por los elementos comunes entre A y B.

Suponiendo la gramatica G=({0,1},{A,B}, A, P), donde P={A:=181), (A:=11), (B.=0)}, Es posible decir que G. Una gramatica independiente del contexto (tipo 2). Una gramatica independiente del contexto (tipo 1).

Para que se utilizan los automatas finitos generalmente? Seleccione los dos opciones correctas. Para verificar que las cadenas pertenecen a un lenguaje Como un analizador durante una parte del porceso de compilacion de un lenguaje de alto nivel. Para reconocer cadenas de todo tipo de lenguajes.

La union de un numero arbitrario finito de alfabetos da como resultado. Un alfabeto identico al que tiene mayor nuemrode simbolos. Un alfabeto valido.

Un automata finito determinnista puede tener solamente un estado de aceptacion. Verdadero. Falso.

Una maquina de Mealy es una maquina secuencial en la que la salida se produce. En cada estado. Durante la transicion.

Con respecto a las expresiones regulares, ¿cuales de las siguientes afirmaciones son correctas? Selecciones las tres correctas. Si a es una expresion regular (a) es una expresion regular Si a es una expresion regular, a* es una expresion regular Si a es una expresion regular a.b es una expresion regular aun si b no es regular. Si a es una expresion regular (a) es una expresion regular Si a es una expresion regular, a* es una expresion regular.

Dados dos lenguajes L1 sobre el alfabeto Z1 y L2 sobre el alfabeto Z2, la concatenacion de L1 con L2 (L1 L2) se define como: L1 . L2 =(y.x /Y ε L2, x εL1). L1 . L2 =(y.x /Y ε L1, x εL2).

Dos gramaticas son equivalentes si: Generan el mismo lenguaje. Generan cancer de hipotalamo.

Una garmatica es recursiva si: Tiene porducciones recursivas tanto por derecha como por izquierda. Tiene al menos una produccion recursiva.

Con respecto al lenguaje reconocido, es posible afirmar que: Los automatas finitos son capaces de reconocer palabras pertenecinetes a cualquier tipo de lenguaje. Los automatas finitos son capaces de reconocer solamente cadenas pertenecinetes a lenguajes generados por gramatica de tipo 3.

La funcion de transicion de estado en la maquina de Mealy se define como: Q x Σe ---> Q. Quca.

Dado el siguiente diagrama de estados que representa un automata finito es posible afirmar que: 0 1 A------>B--------->C <--------- λ 1 0 F. Se trata de un automata finito determinista que acepta cadenas que inician con cero y termina con uno. Se trata de un automata finito no determinista que acepta la cadena vacia o cadenas que inician con cero termina con uno y no tienen simbolos iguales consecutivos.

Si E1 y E2 son expresionesregulares, ¿cuales de las siguientes expresiones tambien lo son? Seleccione las 4 correctas. E1 I E2. E. E1*. E1 . E2. E1 I E2. E1. E1-E2. E1 . E1.

Un sistema de numeracion esta definido por un conjunto de simbolos que pueden concatenarse de modo de representar cantidades. La base del sistema de numeracion coincide con la cantiad de simbolos diferentes del sistema. El sistema puede ser definido mediante una gramatica formal que difiere segun la base del mismo. Si el sistema a definir es el sistema binario. ¡cual de las siguientes gramaticas generaria las cadenas correctas?. ΣNT=(digito, otrodigito, otrodigito, base2, vacio} ΣT(0, 1) P=(base2:=digito otrodigito), (otrodigito:= digito otrofigito, otrodigito), (otrodigito:=vacio), (digito:=0/1), (vacio;=)}. ΣNR=qdigiti{na-noige-nada.

Una gramatica es ambigua si: Si es una gramtica recursiva. Tiene al menos una snetencia ambigua.

Suponiendo un automata finito con la siguiente tablade transicion: estado0.1>s0* s1 s0s1 s1 s1 ¿que clase de palabras son aceptadas por el automata?. Cadenas formadas por sentencia de ceros y unos alternados de al menos dos simbolos. Cadenas formadas por secuencias de unos de cualquier longitud, incluyendo la cadena vacia.

Seleccione las tres respuestas correctas. Por definicion una gramatica es ana cuadrupla cuya expresion formal es G=Σt, S, P). Con base en esta definicion indique cuales de las siguientes afirmaciones son correctas. Σt= alfabeti de los simbolos terminales, Σnt alfabeto de los simbolos no terminales, S= es el axioma y P las reglas de derivacion Σt= alfabeto de los simbolos terminales, Σnt= alfabeti de los simbolos no terminales, S= es un simbolo no terminal y P es un conjunto de reglas. x=alfabeto de los simbolos incas y mayas del siglo 15.

Para diseñar un sistema de control es necesario craer una gramatica tal que el lenguaje generado consista en palabras sobre.. con un conjunto de 1s seguido de un conjunto de 0s, con la condicione que la cantidad de 1 sea impar y la cantidad de 0 sea par. ¡cual es la gramatica necesaria asumiendo que el axioma es Exp?. (Exp;=unos ceros), (ceros: = ceros 00 I 00), (Unos: = unos 11 I 1). cbu alias: ldn.servicio.tecnico.

Dado el siguineta automata, representado por la tabla de transicion, ¡cual o cuales de los estados pueden eliminarse por ser no conexos? a b ->Q0 Q1 Q3 Q1 Q0 Q3 Q2 Q1 Q4 Q3 Q5 Q5 Q4 Q3 Q3 Q5 Q5 Q3. Los estados Q2 y Q4 no son accesibles desde el estado inicial Q0, por lo tanto pueden eliminarse sin causar modificaciones al automata finito. Los estados Q1 y Q6 son accesibles.

El numero minimo de estados de un automata finito determinista es: Depende del alafbeto de los simbolos de entrada. Uno.

Sea el alfabeto Σ = (1, 2, 3), ¡cual de las siguientes cadenas pertenece a L(Σ)?. c=312. c=134.

La union de un numero arbitrario finito de alfabetos da como resultado: Un alfabeto valido. Un albertonto.

Una maquina de Mealy es una maquina secuencial en la que la slaida se produce: Durante la transicion. Durante el pleno acto.

una maquina de Mealy es una maquina secuencial en la que las salida depende: Del estado actual y del estado inicial de la maquina. Del simbolo de entrada y del estado actual de la maquina.

Una maquina de Mealy es: Una maquina secuencial que genera salidas. Una maquina del futuro.

En un automata finito determinista un estado se dice no conexo si: No puede ser alcanzado desde el estado inicial, independinetemente de la cadena de entrada. No se puede alcanzar desde la base.

De acuerdo con la clasificacion de Chomsky para las gramaticas formales, para que la gramatica sea de tipo 2: En la parte izquierda de las producciones puede haber solo un unico simbolo no terminal. En la parte derecha de las producciones puede haber solo un unico simbolo no terminal.

Una produccion es una regla compresora si: La parte derecha tiene menos o igual cantidad de simbolos que la parte izquierda La parte derecha tiene un simbolo terminal. la parte derecha es la cadena vacia (A) La parte derecha tiene menos simbolos que la parte izquierda.

El lenguaje aceptado por un automatafinito no determinista esta formado: Por cualquier cadena formada por elementos que pertenecen al alfabeto de los simbolosde entrada. Por todas las cadenas formadas con simbolos del alfabeto de entrada, que partiendo desde el estado inicial, hacen que el.... estados finales.

De acuerdo con la clasificacion de Chomsky para las gramaticas formales, para que la gramatica sea de tipo 3: En la parte izquierda de las producciones puede haber solo un unico simbolo no terminal. Las producciones deben tener la forma S:=λ, A:=a (no terminal que deriva en terminal) o A:=aB (no terminal que deriva en terminal seguido de no terminal).