Lenguaje Formales y Computabilidad

Sean A y B Conjuntos; A qué se llama una relación de A en B?. Un subconjunto R del producto cartesiano AxB. Un.

Que se requiere para definir un autómata finito determinista?. Seleccione 4 opciones correctas. Identificar el estado inicial y los estados finales. Explicitar la función de transición de estados. Identificar alfabeto de entrada y conjunto de estados. Generar el diagrama de estados del autómata. U.

Si el alfabeto Σ = (1,2,3) . Cuál de las siguientes cadenas ∈ L(Σ). c=312. U.

Si E1 y E2 son dos Expresiones regulares; E1 + E2 es una expresión regular. Verdadero. Falso.

Suponiendo la gramática G= ({0,1}, {A,B,C}, A, P), donde P={ (A:=1B), (B:=1), (B:=0C), (B:=1C), (C:=1)}. Es posible decir que G es: Una gramática regular o lineal (tipo 2). Una gramática regular o lineal (tipo 1). Una gramática regular o lineal (tipo 3).

Mateo es estudiante de una carrera de informática y está muy interesado en las propiedades de las gramáticas formales y de los lenguajes que estas generan. Estuvo analizando la gramática formal de G=(Σt, Σnt, S, P), donde Σt= (0,1), Σnt=(S), S es el axioma y P={(S:=0S), (S:=1S), (S:=λ)} y concluyó que el lenguaje general es un lenguaje general de la forma L=[(0+1)*]. Cuál de las siguientes consideraciones realizó Mateo para poder llegar a su conclusión?. (4) Cuatro opciones son correctas. Las palabras generadas por G constan de cualquier cantidad de 1 y 0 en cualquier posición. Si se realizan derivaciones sobre la gramática G se obtiene entre otras la siguiente palabras: 0,1,001, 00111, 0000100101, 00000111, etc. La gramática G es una gramática regular, por lo tanto el Lenguaje generado es también regular. La gramática G es una gramática lineal, por derecha. U.

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. 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 determinista que acepta la cadena vacía o cadenas que inician con cero, termina con uno y no consecutivos. Se trata de un autómata finito determinista que acepta la cadena vacía o cadenas que inician con cero, termina con uno iguales consecutivos.

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

De acuerdo con la clasificación de Chomsky para las gramáticas formales, para que la gramática sea de tipo 2: Las partes derecha e izquierda de las producciones deben tener algo en común. En la parte izquierda de las producciones puede haber solo un único símbolo no terminal.

Un autómata finito determinista se define formalmente mediante la quíntupla AFD= (Σ,Q,q0,F,f) donde F representa: El alfabeto de los símbolos de salida. El conjunto de los estados finales del autómata.

Dados dos lenguajes L1 sobre el alfabeto Σ1 y L2 sobre el alfabeto Σ2, la resta L1 menos L2 (L1-L2) se define como: L1 - L2 = { x / x pertenece a L1 y x no pertenece a L2}. UU.

Sea A un conjunto, se dice que un conjunto B está contenido en A y se nota B ⊆ A, si: Si todo elemento de B es también un elemento de A. UU.

Dado un autómata finito determinista se dice que dos estados p y q son equivalentes entre sí: La transiciones a partir de los estados p y q para la misma cadena x llevan al mismo estado s. Las transiciones tanto desde p como desde q con una secuencia de símbolos x llevan un estado final y las transiciones desde p como desde q con una secuencia y llevan un estado que no es un estado final.

Cuáles de las siguientes afirmaciones sobre los autómatas finitos son correctas? Selecione 4 opciones correctas: En un autómata finito no determinista puede haber cer, una o más transiciones desde un estado leyendo el mismo símbolo de entrada, que conduzca a estados diferentes al mismo. Un autómata finito es capaz de reconocer cadenas que pertenecen a un lenguaje generado por una gramática regular. En un autómata finito determinista para cada estado existe exactamente una transición por cada símbolo del alfabeto de la máquina. Los autómatas finitos tienen un número finito de estados. uuu.

La clausura positiva de un lenguaje L sobre un alfabeto Σ se define como: La unión de todas las potencias del lenguaje excluyendo la potencia 0. uuu.

Sean A y B conjuntos, la unión de A y B (denota A ∪ B) es un conjunto que cumple con: Ser el conjunto de todos los elementos que están en A o en B. uuu.

Para un proyecto de informática es necesario crear una gramática que permite generar palabras con tre o más ceros consecutivos. Cuáles serían las producciones que peritarían generar el lenguaje descripto sabiendo que el alfabeto es Σt=(0,1)?. (S:=0A|1S), (A:=0B|1S), (B:=0C|1S), (C:=0C|1S). (S:=0A|1S), (A:=0B|1S), (B:=0C|1S), (C:=0C|1S|λ).

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 = {x.y / x ∈ L1, y ∈ L2}. uuu.

La clausura positiva de un Lenguaje L sobre un alfabeto Σ se define como: El universo del alfabeto Σ. La unión de todas las potencias del lenguaje incluyendo la potencia 0. La unión de todas las palabras del lenguaje incluyendo a 0 como potencia. La concatenación del lenguaje con sí mismo. La unión de todas las potencias del lenguaje excluyendo la potencia 0.

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

Si el alfabeto Σ = (0,1) (alfabeto binario) y será v y w palabras v* tales que v=111, w=1110. Cuál es el resultado de la operación y=v.w ?. y= 01111110. uuu.