TALF
![]() |
![]() |
![]() |
Título del Test:![]() TALF Descripción: buen tiempo empleado Fecha de Creación: 2018/02/03 Categoría: Otros Número Preguntas: 202
|




Comentarios |
---|
NO HAY REGISTROS |
Si un conjunto es vacio su funcion caracteristica. Siempre vale uno. Siempre vale cero. No existe. En una composicion. El numero de funciones internas y externas puede coincidir. Siempre hay mas funciones internas que externas. Siempre hay mas funciones externas que internas. Marca la afirmacion verdadera: x≠ x^(R) e y ≠ y^(R) ⇒ xy ≠ yx, ∀x, y ∈ Σ*. (wx)^(R) = x^(R) w^(R), ∀x, w ∈ Σ*. (wx)^(2) = w^(2) x^(2), ∀x, w ∈ Σ*. Si R es una relacion de equivalencia y D su conjunto diagonal entonces: ||D|| = 0. ||D|| ∉ N. ||D|| > 0. Si A = {1,2,3} entonces. {A} ⊂ 2^(A). {0} ⊂ 2^(A). A^(2) ⊂ 2^(A). Si A = {1,2,3} y B { {1}, {2,3}} entonces: B es el conjunto potencia de A. B es una particion de A. B es un subconjunto de A. El cardinal del conjunto potencia de un conjunto: Solo es cero si el conjunto es el vacio. Es cero si el conjunto es finito. Nunca es cero. Para toda relacion R, su cierre reflexivo es: R ∪ R^(-1). R ∪ I. R - I. El cierre simetrico de una relacion R esta definido como: R ∪ R^(-1). R ∪ I. R ∩ I. Marca la afirmacion verdadera. Si f es una funcion biyectiva, entonces || Dom(f) || = || Rg(f) ||. Si f es una funcion biyectiva, entonces Dom(f) = Rg(f). Si || Dom(f) || = Rg(f) ||, entonces f es una funcion biyectiva. Sea Σ = {a,b,c,d}. Una expresion Regular para el lenguaje L = { w ∈ Σ* tal que |w| = n || Σ ||, n ≥ 0 } es: ((a+b+c+d) (a+b+c+d)(a+b+c+d))*. ((a+b+c+d) (a+b+c+d)(a+b+c+d)(a+b+c+d))*. (a+b+c+d)*. Los automatas con pila no deterministas. generan lenguajes de tipo 1. reconocen lenguajes de tipo 2. no pueden alcanzar estados de bloqueo. Marca la opcion incorrecta. Toda GCL tiene al menos un simbolo accesible. Toda GCL tiene al menos un simbolo util. Una gramatica puede tener un simbolo que sea accesible, terminable e inutil. L(APND) =. L.3. L(AFD). L.2. Dada una gramatica, G = (N,T,P,S). S ∈ T. S ∈ N. N ∈ S. Si M ( {s,f}, {a,b}, {a,b}, { (( s,aa, ∈), (s,b)), ((s,∈,∈), (f,∈)), ((f,a,b), (f,∈))}, s, {f}) entonces. L(M) = {ww^(R) | w ∈ {a,b}* }. L(M) = {www^(R) | w ∈ {a,b}* }. L(M) = {w ∈ {a,b}* | w = a^(3n) con n ∈ N }. Los lenguajes de contexto libre son cerrados para las operaciones de: union, concatenacion, estrella de Kleene. union, concatenacion y complemento, estrella de Kleene e interseccion. union, concatenacion, complemento. Una gramatica es propia si. no es recursiva ni ambigua y no tiene simbolos inutiles. no es recursiva izquierda y no tiene simbolos inutiles. no es recursiva y no tiene simbolos inutiles. Si una GCL es recursiva por la izquierda, entonces. genera un lenguaje infinito. existe una GCL equivalente que no es recursiva por la izquierda. existe una gramatica regular equivalente. Marca la opcion verdadera. Toda GRI esta en FNG. Una gramatica recursiva por la izquierda puede estar en FNG. Una gramatica de tipo tres siempre esta en FNC. Si un lenguaje no es regular entonces siempre se verifica. no puede representarse con un AFD. no cumple la CBR. no es sensible al contexto. Dados L ⊆ Σ* y x,y ∈ Σ*. Si (xz ∈ L ^ yz ∈ L) ∀z ∈ Σ* entonces: |xy| > |z|. L no es un lenguaje regular. x e y son indistingibles. si a, β ∈ ER, entonces. a + (β) ∈ ER. (( a* β* + β*) ∈ ER. *(aβ)* ∈ ER. Cuando, al menos, una cadena de un lenguaje generado por una GCL es el producto de mas de un arbol de derivacion,. la gramatica es ambigua. la cadema es de tipo ww^(R). el lenguaje es regular. si x, y ∈ Σ* y son indistinguibles respecto a L, entonces ∃ z ∈ Σ* tal que. (xz ∈ L ∧ yz ∉ L) ∨ (zx ∉ L ∧ zy ∈ L). (xz ∈ L ∧ yz ∈ L) ∨ (xz ∉ L ∧ yz ∉ L). (zx ∈ L ∧ zy ∈ L) ∨ (zx ∉ L ∧ zy ∉ L). El teorema de Myhill-Nerode se suele utilizar para demostrar que un lenguaje. es de tipo 0. es de tipo 2 y no es de tipo 3. no es regular. Si un lenguaje cumple la condicion de bombeo regular entonces. no hay un AFD que lo represente. puede representarse con una expresion regular. no podemos afirmar que es regular. L = {0^(N) 1^(N)}. cumple la CBR. es un lenguaje de tipo 1. es un lenguaje regular. (q0, baababaaa) ├ (q1, ababaaa) ├ (q3, babaaa). es una computacion de un posible AFND. es una computacion completa. es una computacion de un posible AFD. En un AFND una configuracion. es una terna perteneciente a K x Σ* x K. es un par perteneciente a K x Σ^(+). es un par perteneciente a K x Σ*. Si un AFD rechaza una cadena w: lo hace en |w| pasos o menos. lo hace en |w| + 1 pasos. lo hace en exactamente |w| pasos. Si un AFD acepta un lenguaje finito L entonces. el afd no tiene ningun estado inaccesible. el cardinal del lenguaje es menor que el numero de estados del AFD. el estado inicial no es final. Identifica la expresion falsa. L(AFND) = L.3. ||L(AFND)|| es no numerable. ||L(AFND) || = || L(AFD) ||. Un AFND transita en funcion de. el estado actual y el primer simbolo de la cadena. un estado actual y un prefijo de la cadena. el proximo estado. Cuando un AF alcanza una configuracion terminal. queda bloqueado. acepta la cadena. podria transitar, pero solo si es determinista. En un diagrama de estados de un AFND. es un grafo no dirigido y etiquetado. una etiqueta representa la subcadena consumida. los estados se representan con dobles circulos. Sea G = (N,T,P,S) con N = {A,B}, T = {0,1}, P = { A → 1100A | 0B | 0, B → 0B | 0}, S=A ¿Cual de los siguientes lenguajes es el lenguaje generado por G?. (1100)* 0 0*. (1100)* 0. (1100)* 00 0*. Sea Σ = {a.b.c}. Dado L = {w ∈ Σ^(*) | aa no es una subcadena de w }, una ER del mismo es: L = (b+c)* a ( (b+c) a)* (b+c)*. L = (b+c)* (a+∈) (b+c) (a+∈). L = (b+c)* (a+∈) ( (b+c) (a+∈)* ) (b+c)*. Si un conjunto es equipotencial con el conjunto de los numeros naturales pares, dicho conjunto: tiene cardinal par. tiene ℵ1 elementos. es infinito. En un AFD el lenguaje aceptado. nunca incluye la cadena vacia. puede incluir la cadena vacia. si incluye la cadena vacia entonces el lenguaje es infinito. Sea G = (N,T,P,S) con N = {A,B}, T ={0,1}, P = {A →1100A | 0B | 0, B → 0B | 0}, S=A ¿ de que tipos (0,1,2,RI,RD,L,LI,LD) es la gramtica?. Tipos 0,1,2,L,R. Tipos 0,1,2,L y LI. Tipos 0,1,2, L y LD. ¿Cual de las siguientes expresiones identifica un lenguaje sobre un alfabeto Σ?. 0. {Σ^(+)}. ||Σ||. sean x e y cadenas sobre un alfabeto Σ. Se cumple que xy = yx si: x = y. x = y^(R) e y ≠ ∈. x = x^(R) e y = y^(R). Marca la afirmacion verdadera. ∀L ⊆ Σ*, L x L^(R) = ( L^(R) x L)^(R). ∀L ⊆ Σ*, L* ∩ L* R ≠ Ø. ∀ L_1, L_2 ⊆ Σ*, L_1^(R) x L_2^(R) = ( L_1 x L_2 )^(R). Marca la afirmacion verdadera. Todo lenguaje no representable es no numerable. Todo lenguaje no representable es la union de infinitos lenguajes representables. El complementario de un lenguaje no representable puede ser representable. Marca la afirmacion verdadera: La regla ABA → BABA es sensible al contexto. La regla AB → BA es sensible al contexto. La regla a → aB es de tipo 1. Una gramatica es. una forma de representar lenguajes. un subconjunto de L.REP. un algoritmo conclusivo para reconocer lenguajes. Marca la afirmacion falsa: Ø* = {ɛ}*. Ø^(ɛ) = {ɛ}^(Ø) = {ɛ}. ɛ ∈ L ⇔ L^(+) = L*. La regla a → a (donde a es un simbolo terminal) es. de tipo 0 y no es de tipo 1. de tipo 1 y no es de tipo 2. de tipo 2 y no es de tipo 3. Si G = (N,T,P,S) es regular izquierda y regular derecha a la vez, entonces. || L(G)|| ≤ ||T||. || L(G) || ≥ 1. || L(G)|| = 0. Si G (N,T,P,S) es lineal izquierda y lineal derecha a la vez, entonces. ||L(G) || ≤ ||P||. ||L(G) || ≤ ||T||. ||L(G) || ≠ 0. Marca la afirmacion verdadera. Si (∀ x,y ∈ Σ* |x| < |y| ⇒ x es prefijo de y ) entonces || Σ || = 1. si x e y son cadenas sobre un alfabeto, entonces xy = yx ⇒ x = y. si una cadena x es sufijo y prefijo de otra cadena y entonces x = y. Marca la afirmacion verdadera. x ≠ x^(R) e y ≠ y^(R) ⇒ xy ≠ yx, ∀x, y ∈ Σ*. (wx)^(R) = x^(R) w^(R), ∀ x,w ∈ Σ*. (wx)^(2) = w^(2) x^(2), ∀ x,w ∈ Σ*. El conjunto de todos los lenguajes sobre un alfabeto es. finito. infinito no numerable. infinito numerable. El conjunto de todos los posibles lenguajes representables sobre un alfabeto es: finito. infinito no numerable. infinito numerable. La gramatica G = ({S}, {b}, {SS → bS}, S) es. de tipo 0 y no de tipo 1. de tipo 1 y no es de tipo 2. de tipo 2 y no es de tipo 3. Si A={1,2} y B={3,4}, entonces R ={(1,4),(2,3)}. no es una aplicacion de A a B. es una funcion biyectiva de A a B. es una funcion parcial de A a B. El cierre amplio de un conjunto para una operacion. incluye su cierre estricto. no incluye el elemento neutro. no inclue el conjunto vacio. Elija la opcion correcta. ||N|| = 2^( ℵ0). ||Q|| = 2^( ℵ0). ||R|| - ||N|| = 2^( ℵ0). Marca la afirmacion verdadera: Todo conjunto numerable es equipotencia con N. Un conjunto no numerable no tiene ningun subconjunto infinito numerable. No todo subconjunto infinito de un conjunto no numerable es no numerable. Dados A = {1,2,3}, B = {4} y R {(1,4)}, se cumple que : R es una relacion de equivalencia sobre A. R es una relacion binaria sobre A. R es un subconjunto de A x B. Sean M = (K, Σ, Δ, s, F) ∈ AFD, (q,w) y (q', w') configuraciones de M. Si (q,w) ├ (q', w'), entonces. ∃ σ ∈ Σ | (w, = σw' ) ∧ (δ (q,σ) = q'). ∃ σ ∈ Σ | (w' = σw) ∧ (δ (σ,q) = q'). ∃ σ ∈ Σ | (w = σ'w) ∧ (δ (q',σ) = q). Si A = {1,2,3} y R={(1,1),(2,2)}entonces. R es una relacion de equivalencia sobre A. R es una relacion reflexiva sobre A. R es una relacion simetrica sobre A. Sea el monoide (N,+) y sea B ⊆ N. Si B = B^(+) ∧ ||B|| >1, entonces: ||B|| ∈ N. ||B|| = 2. ||B|| = ℵ0. Si R es una relacion de equivalencia y D un conjunto diagonal entonces: ||D|| = 0. ||D||∉ N. ||D|| > 0. L = {0^(n) 1^(n)}. cumple la CBR. es un lenguaje de tipo 1. es un lenguaje regular. Si un lenguaje no es regular entonces siempre se verifica que: no puede representarse con un AFD. no cumple la CBR. no es sensible al contexto. Dados L ⊆ Σ* y x,y ∈ Σ*. Si (xz ∈ L ∧ yz ∈ L) ∀z∈ Σ* entonces. |xy| > |z|. L no es un lenguaje regular. x e y son indistinguibles. Marca la afirmacion verdadera. El complementario de un lenguaje no representable puede ser representable. Todo lenguaje no representable es no numerable. Todo lenguaje no representable es a la union de infinitps lenguajes representables. La regla a → a (donde a es un simbolo terminal) es. de tipo 2 y no es de tipo 3. de tipo 0 y no es de tipo 1. de tipo 1 y no es de tipo 2. Marca la afirmacion verdadera. Todo lenguaje regular es finito. Todo lenguajes es numerable. Todo lenguaje no representable es no numerable. Si α y β son expresiones regulares sobre un alfabeto, entonces. α* (βα)* = (α + β)*. (αββ*)* = (α*αβ)*. (α + Ø = (Ø* α). Sea G =(N,T,P,S) con N ={S,A}, T = {a,b}, P = S → A |aSA |bSA, A → a| b}. ¿ que lenguaje genera?. L(G) = {w ∈ T* tal que w = a^(n) b^(n), con n ≥ 0}. L(G) = {w ∈ T* tal que w = 2n, con n ≥ 0}. L(G) = {w ∈ T* tal que w = 2n + 1, con n ≥ 0}. ¿Es posible que ∀L ⊆ Σ* se cumpla que L = L^(R)?. si, cuando el cardinal de Σ es dos. si cuando el cadinal de Σ es uno. no, ya que el cardinal de Σ ni puede ser cero. Si G = (N,T,P,S) es lineal izquierda y lineal derecha a la vez, entonces. ||L(G)|| ≤ ||T||. ||L(G)|| ≤ ||P||. ||L(G)|| ≠ 0. Marca la afirmacion falsa: La regla ABA → BABA es sensible al contexto. La regla AA → BB es de tipo uno. La regla ABA → BBA es sensible al contexto. Si A y B son conjuntos no numerables, entonces: A - B puede ser numerable. A - B siempre es no numerable. A - B siempre es numerable. Marca la afirmacion falsa: Solo los lenguajes finitos pueden ser representados por una expresion regular. Todas las gramaticas regulares generan lenguajes que son representables mediante expresiones regulares. No todo lenguaje puede ser representado por una expresion regular. Dada una gramatica G = (N,T,P,S), se cumple que: N ∩ T = V. N ∩ T = 0. N ∩ T = S. Si G = (N,T,P,S) es regular izquierda y regular derecha a la vez, entonces. ||L(G)|| ≤ ||T||. ||L(G)|| ≥ 1. ||L(G)|| = 0. ¿Cual de las siguientes expresiones identifica un lenguaje sobre un alfabeto Σ?. ||Σ||. {Σ^(+)}. 0. Sea R una relacion sobre un conjunto A. R ∪ R^(-1) es: la relacion de identidad. 0. el cierre simetrico de R. Marca la afirmacion verdadera: si x e y son cadenas sobre un alfabeto, entonces xy = yx ==> x = y. si (∀ x,y ∈ Σ* |x| < |y| ==> x es prefijo de y ) entonces ||Σ|| = 1. Si una cadena x es sufijo y prefijo de otra cadena y entonces x = y. La gramatica ({A} , {a}, {A →Aa}, A). genera la derivacion a ⇒ Aa ⇒ Aaa ⇒ aaa. es regular izquierda. representa el lenguaje L={ }. Sean x e y dos cadenas, entonces x·y. tiene longitud ≥ que la de x. es un conjunto infinito. contiene |x| x |y| simbolos. El cardinal del conjunto potencia de un cojunto. nunca es cero. es cero si el conjunto es finito. solo es cero si el conjunto es el vacio. Si R es una relacion de equivalencia y D su conjunto diagonal entonces: ||D|| = 0. ||D|| ∉ N. ||D|| > 0. Marca la afirmacion verdadera. si f es una funcion biyectiva entonces ||Dom(f) || = ||Rg(f)||. si ||Dom(f) || = ||Rg(f)||, entonces f es una funcion biyectiva. si f es una funcion biyectiva, entonces Dom(f) = Rg(f). Para toda relacion R, su cierre reflexivo es: R ∪ I. R ∪ R-1. R- I. Marca la afirmacion verdadera. ∀L ⊆ Σ*, L* ∩ L* R ≠ Ø. ∀L ⊆ Σ*, L· LR = (LR · L) R. ∀L1 , L2 ⊆ Σ*, LR1 · LR2 = (L1 · L2) R. Marca la afirmacion verdadera. si una cadena x es sufijo y prefijo de otra cadena y entonces x = y. si x e y son cadenas sobre un alfabeto, entonces xy = yx ==> x = y. si (∀ x, y ∈ Σ* |x| < |y| ==> x es prefijo de y ) entonces ||Σ|| = 1. La gramatica G = ( {S}, {b}, {SS→bS}, S) es. de tipo 1 y no es de tipo 2. de tipo 2 y no es de tipo 3. de tipo 0 y no es de tipo 1. Si una GCL es recursiva por la izquierda, entonces. genera un lenguaje infinito. existe una gramatica regular equivalente. existe una GCL equivalente que no es recursiva por la izquierda. Marca la afirmacion falsa. Si L es un lenguaje regular entonces cumple la CBLC. Si L es un lenguaje regular entonces cumple la CBR. Si L cumple la CBCL entonces es un lenguaje de tipo 2. Si un AFD acepta un lenguaje finito L entonces. el AFD no tiene ningun estado inaccesible. el estado inicial no es final. el cardinal del lenguaje es menor que el numero de estados. Un APND, con un conjunto de estados finales F, acepta una cadena w si y solo si. ∃ q ∈ F / (s,ɛ,w) Ͱ (q,ɛ,ɛ). ∃ q ∈ F / (s,w,ɛ) Ͱ* (q,ɛ,ɛ). ∃ q ∈ F / (s,w,ɛ) Ͱ (q,ɛ,ɛ). El conjunto de configuraciones iniciales de un AFD definido por ( K, Σ, δ, s, F): tiene el mismo cardinal que K. tiene el mismo cardinal que F. es infinito. Si M es un AFDM entonces. todos los AFD queivalentes tienen mayor o igual numero de estados que M. todos los AFD equivalentes tienen menos estados finales que M. existe un AFD equivalente con menos estados que M. El conjunto de configuraciones terminales de AFD definido por (K,Σ,δ,s,F). tienen el mismo cardinal que F. tiene el mismo cardinal que K. es infinito. Sea m un APND. si ninguna computacion de M altera el contenido de la pila entonces L(M) ∈ L.3. una computacion terminada de M puede estar bloqueada. si acepta la cadena vacia entonces el estado inicial es tambien final. En un diagrama de estados de un AFND. una etiqueta de un arco representa la subcadena consumida. los estados se representan con dobles circulos. puede haber mas de un estado inicial. L(AFD) =. L(AFND). L(APND). L.2. En un AFND una configuracion. es un par pertenenciente a K x K^(+). es un par perteneciente a K x K*. es una terna perteneciente a K x K* x K. Si dado un lenguaje L ⊆ Σ*, todas sus cadenas son indistinguibles entre si, entonces. L = Σ*. L = 0. L = Σ* ∨ L = 0. Si M = ( {s,f}, {a,b}, {a,b}, {(( s,aa, ε), (s,b)), ((s,ε,ε), (f,ε)) ((f,a,b), (f,ε))}, s, {f} ) entonces. L(M) = {w ∈ {a,b}* | w = a^(3n) con n ∈ N}. L(M) = {www^(R) | w ∈ {a,b}* }. L(M) = {ww^(R) | w ∈ {a,b}* }. Un AFND transita en funcion de. un estado y un prefijo de la cadena. el estado actual y el primer simbolo de la cadena. el proximo estado. Un AFDM. tiene menos estados que cualquier AFND equivalente. no puede tener estados inaccesibles. puede tener configuraciones de bloqueo. En un AFD: tiene que haber tantas computaciones completas como cadenas aceptadas. puede haber mas computaciones completas que cadenas aceptadas. puede haber menos computaciones completas que cadenas aceptadas. Los automatas con pila no deterministas. no pueden alcanzar estados de bloqueo. generan lenguajes de tipo 1. representan lenguajes de tipo 2. El teorema de Myhill-Nerode se suele utilizar para demostrar que un lenguaje. es de tipo 2 y no es de tipo 3. es de tipo 0. no es regular. Una GCL es ambigua sii. ∀ w ∈ L(G) / w es producto de mas de un arbol de derivacion. ∀ w ∈ L(G) / w es producto de infinitos arboles de derivacion. ∃ w ∈ L(G) / w es producto de mas de un arbol de derivacion. Un AFD M. decide si una cadena pertenece o no a L(M). contiene infinitos estados. puede representar cualquier lenguaje de tipo2. Respecto a la operacion de union de lenguajes. los lenguajes sensibles al contexto no son cerrados. solo son cerrados los lenguajes regulares y de contexto libre. los cinco tipos de lenguajes son cerrados. Si A = {1,2,3} y B ={{1},{2,3}} entonces: B es una particion de A. B es el conjunto potencia de A. B es un subconjunto de A. Las expreseiones regulares. pueden representar cualquier lenguaje representables. no pueden representar lenguajes que incluyen la cadena vacia. pueden representar cualquier lenguaje de tipo 3. Dado un lenguaje L: L { ɛ } = L. L { ɛ } = LØ. L { ɛ } = ØL. De acuerdo con la clasificacion de los lenguajes, se cumple que: lenguajes de tipo 3 ⊂ lenguajes de tipo 0. lenguajes con estructura de frase ⊂ lenguajes de tipo 2. lenguajes lineales ⊂ lenguajes regulares. ¿ En cual de los siguientes casos la gramtica sera del tipo "independiente del contexto"?. si todas sus reglas son de tipo 1. si al menos una de sus reglas es sensible al contexto. si todas sus reglas son regulares terminales. Una gramatica es. un algoritmo conclusivo para reconocer lenguajes. una forma de representar lenguajes. un subconjunto de L.REP. El cadinal de las funciones computables es: menor que el de las funciones no calculales. mayor que el de las funciones representables. menor que el de las funciones totales. Toda GCL que esta en FNC cumple que. ninguna regla tiene en la parte derecha mas de dos simbolos. ninguna regla tiene en la parte derecha menos de dos simbolos. todas las reglas tienen en la parte derecha exactamente dos simbolos. El AFD M = (K,Σ,δ,s,F) con K (q0, q1) y Σ={0,1}, con la funcion de transicion especificada por: δ(q0,0) = q1, δ(q0,1) = q0, δ(q1,0) = q1, δ(q1,1) = q0, y con s = q0 F=q1, representa: un lenguaje con infinitas cadenas cuyo ultimo simbolo es 0. un lenguaje con infinitas cadenas que no contienen 0. el conjunto vacio. Elija la opcion correcta. ||N|| = 2 ^( ℵ0). ||R|| - ||N|| = 2^(ℵ0). ||Q|| = 2^(ℵ0). Dada una gramatica G(N,T,P,S) se cumple que: N∩T = 0. N∩T = S. N∩T = V. Dada una gramatica, el conjunto de reglas de produccion P cumple que: P = N ∩ T. P ⊂ (N ∪ T)^(+) x (N∪T)*. P ⊂ (N ∪ T)*. Dada una gramatica de tipo 2, siempre podemos responder si: el lenguaje que representa es vacio. es equivalente a otra gramatica de tipo 2. existe una gramatica regular equivalente. El teorema de Myhill-Nerode suele usarse para: demostrar que el lenguaje no es vacio. demostrar que el lenguaje es regular. demostrar que un lenguaje no es regular. Si en un lenguaje L sobre Σ* todas sus cadenas son indistinguibles, entonces. L = Σ*. L = 0. L = Σ* o L = 0. si v es una cadena y w es su inversa, entonces. No siempre todos los sufijos de v son prefijos de w, pero si al menos uno. Hay casos en los que no coincide ningun sufijo de v con ningun prefijo de w. Todos los sufijos de v son prefijos de w. El conjunto de los cardinales delos conjuntos infinitos es: infinito numerable. infinito no numerable. finito. ¿Cuantos lenguajes distintos hay, sobre un alfabeto dado, que puedan ser reconocidos por un AFD con un solo estado?. Dos. El cardinal del alfabeto. Infinitos. Si α es una expresion regular, entonces. α* - αα* = {ε}. α* - αα* = α. α* - αα* = Ø. Sea L = {w ∈ {0,1}* | w = 0* 1*. las cadenas r = 00 y s =001 son distinguilbes porque rz ∈ L y sz ∉ L con z = 0. Las cadenas r = 00 y s =001 son indistinguibles porque rz y sz pertenecen al lenguaje cuando z = 1. El lenguaje no es regular porque ||ΠL|| ∉ N. Si una gramatica G es la vez regular izquierda y regular derecha entonces L(G) es: cualquier lenguaje regular. cualquier lenguaje finito. cualquier subconjunto del alfabeto terminal de la gramatica. Dado el siguiente automata de pila: AP = {K = q0,q1,q2,q3}, Σ ={a,b,c}, Γ = Σ ∪ {#}, Δ,q0, F={q3}}, donde: Δ(q0,ɛ,ɛ) = (q1,#) Δ(q1,a,ɛ) = (q1,a) Δ(q1,b,ɛ) = (q2,ɛ) Δ(q2,c,a) = (q2,ɛ) Δ(q2,c,#) = (q3,#) Δ(q3,c,#) = (q3,#) Δ(q3,ɛ,#) = (q3,ɛ). L = {a^(i) bc^(k) | i ≥ 0 ∧ i ≤ k }. L = {a^(i) bc^(k) | i ≥ 1 ∧ i ≤ k }. L = {a^(i) bc^(k) | i ≥ 0 ∧ i < k }. Si una cadena v, de longitud mayor que cerom tiene n sufijos distintos. entonces v^(3) tiene: 3n sufijos distintos. 3n + 1 sufijos distintos. 3n - 2 sufijos distintos. ¿Cual de los siguientes es un lenguaje de contexto libre?. L = {a^(i) b^(j) c^(j) d^(i) | i,j ≥ 0}. L = {a^(i) b^(j) c^(i) d^(i) | i,j ≥ 0}. L = {a^(i) b^(j) c^(j) d^(j) | i,j ≥ 0}. ¿Cual es, dentro de los naturales, el cierre amplio del conjunto de los impares para la operacion suma de naturales?. Los pares. {n ∈ N | n ≥ 1}. Los naturales. ¿Para cuantos lenguajes finitos su cierre estricto coincide con el?. uno. dos. ninguno. El conjunto diagonal de la relacion "mayor que" sobre los naturales. no esta definido al ser los naturales un conjunto finito. es el conjunto de los naturales. es el conjunto vacio. Dado un lenguaje L que no verifica el lema de bombeo para lenguajes de contexto libre: L podria ser generado por un automata finito. L es generado por un automata de pila. En ningun caso L puede ser generado por un atomata finito. La relacion de indistinguibilidad IL definida sobre Σ*. esta definida como: IL = {(x,y) ∈ Σ* x Σ* | x e y son distinguibles con respecto a L }. establece una particion πL tal que ||πL|| ∈ N. es una relacion de equivalencia porque es reflexiva,simetrica y transitiva. ¿Para cuantos lenguajes finitos su Estrella de Kleene coincide con el?. uno. ninguno. dos. Dada una GCL, el numero de simbolos utiles nunca puede ser exactamente igual a: uno. cero. el cardinal del alfabeto terminal. Sea la gramatica G = {{ G,B,C,D}, {a,b}, P,S} con relglas de produccion : S → BC | DD, D → b | SD, B → b, C → a. Entonces: G no puede normalizarse a FNC (Forma Normal de Chomsky). G no esta en FNC pero puede normalizarse a FNC (Forma Normal de Chosmsky). G esta expresada en FNC (Formal Normal de Chosmky). ¿Cual es, dentro de los enteros, el cierre estricto del conjunto {0,1} para la operacion resta de enteros?. Los enteros. {z ∈ Z |z ≤ 1}. {0,1}. El lema de bombeo para lenguajes regulares puede utilizarse para demostrar que: un lenguaje dado es regular. un lenguaje dado no es de tipo 2 y si es de tipo 3. un lenguaje dado no es regular. Dada una gramatica. el lenguaje generado por dicha gramtica es un subconjunto propio de sus formas sentenciales. el lenguaje generado por la gramtica y sus formas sentenciales tienen como interseccion el conjunto vacio. sus formas sentenciales son un subconjunto propio del lenguaje generado por la gramtica. Si un simbolo no terminal de una gramatica G es terminable, entonces se cumple siempre que L(G) =Ø. Verdadero. Solo si el simbolo no terminal es tambien accesible. Falso. Sea L un lenguaje. Sean x ∈ L, y ∉ L. Se cumple que x e y son distinguibles con respecto a L. Verdadero. Falso. Verdadero solo si xy ∉ L. Dada la gramatica G con las reglas: S → aS | bA | ɛ, A → bB | aS | ɛ, B→ aB |bB ¿cual de las expresiones regulares genera el mismo lenguaje definido por G?. b (b (aa*b)*)*. (a + ba)* (ɛ+b). a* (b (aa* b)*)* a. Marca la afirmacion verdadera: Si una cadena x es sufijo y prefijo de otra cadena y, entonces y = xzx. ∀ x,y ∈ Σ tal que |x| = |y| ⇒ x es prefijo de y. si x e y son cadenas sobre un alfabeto, entonces xy = yx ⇒ x = y. Sea el monoide (N,+) y sea B ⊆ N. Si B = B^(+) ∧ ||B||=1, entonces: ||B*||∈ N. ||B*||∈ 2. ||B*||∈ ℵ0. Dado un lenguaje L = {x^(n) y^(n) : n ≥ 0}, el lema de bombeo para los lenguajes regulares permite demostrar que: L es un lenguaje regular. No es posible construir un automata con pila que reconozca L. No es posible construir un automata finito que reconozca L. Si G = (N,T,P,S) es lineal izquierda y lineal derecha a la vez, entonces. ||L(G)|| ≠ 0. ||L(G)|| ≤ ||T*||. ||L(G)|| ≥ ||P||. Si α y β son expresiones regulares sobre un alfabeto, entonces es falso que: (α+0) = (0* α). α* (βα*)* =(α+β)*. ((αββ*)* = α* (βα*)*. Si (q,u,w) es una configuracion de bloqueo de M siendo M un APND, entonces w ∉ L(M). Verdadero, excepto si la configuracion es tambien terminal. Verdadero. Falso. Dado el lenguaje L = {x^(n) y^(m) z^(n) | n ≤ 25∧m ≥ 26} ¿Cual es el tipo de automata mas sencillo (atendiendo a la jerarquia de Chomsky) que puede reconocer dicho lenguaje?. un automata de pila. una maquina de Turing. un automata finito. Si A = {1,2} y B={3,4}, entonces R = {(1,0),(2,3)}. no es una aplicacion de A a B. es una funcion biyectiva de A a B. es una funcion parcial de A a B. ¿Cual de los siguientes lenguajes NO es regular?. cadenas de caracteres con simbolos a separados por 4 * i simbolos, i ≥ 0. L = {w ∈ {a,b}* | abab es subcadena de w}. L = {w ∈ {a,b}* | w ∉ {a^(n) b^(n) : n > 0}. Dados dos lenguajes de contexto libre L1 y L2: L1 ∪ L2 es un lenguaje de contexto libre. L1 + L2 no es un lenguaje de contexto libre. L1 ∩ L2 es un lenguaje de contexto libre. Una configuracion de bloqueo de un APND es aquella que. tiene la pila vacia. no es termina y desde la que no se puede transitar. es de la forma (q,ε,ε). En un AFD. hay tantas configuraciones terminales como estados. todo estado terminal es final. hay tantas configuraciones iniciales como estados. Si A y B son conjuntos no numerables, entonces: A - B siempre es numerable. A - B puede ser numerable. A - B siempre es no numerable. Si A y B son conjuntos numerables, entonces. A y B nunca son equipotenciales. A y B pueden ser equipotenciales. A y B siempre son equipotenciales. Marca la afirmacion verdadera: Toda GRI esta en FNG. Toda GRI esta en FNC. Torda GRD esta en FNG. En la condicion de bombero regular se cumple que. | v | > 0. | v | = 0. | v | ≥ 0. Marca la afirmacion verdadera: La relacion de indistinguibilidad es una relacion binaria sobre L. La relacion de indistinguibilidad es una relacion binaria sobre Σ*. La relacion de indistinguibilidad es una relacion binaria sobre L*. El conjunto de los lenguajes de contexto libre. no es cerrado para la potencia respuesta 2. es cerrado para la interseccion. no es cerrado para el complemento. Una configuracion de un AF es: una quintupla. un par. una terna. Marca la afirmacion verdadera. L cumple la CBBR ⇒ L ∈ L.3. L ∈ L.3 ==> L cumple la CBR. L ∈ L.3 ⇔ L cumple la CBR. Una GCL es ambigua si el lenguaje que genera. sus cadenas son producto de, al menos, un arbol de derivacion. tiene cardinal ℵ0. es inherentemente ambiguo. Si un lenguaje no es regular entonces siempre se verifica que: no es sensible al contexto. no puede representarse con un AFD. no cumple la CBR. Sea G = (N,T,P,S) una GCL en FNC, entonces. ∀ α → β ∈ P, α ∈ N ∧ β ∈ N*. ∀ α → β ∈ P, |α| = 1 ∧ |β| ≤ 2. ∀ α → β ∈ P, α ∈ N ∧ β ∈ T*. ¿Existe una MT con el metodo de operacion ...*w*x*..⇒..*x*w*..?. solo en el caso de que |w| > |x|. no, en ningun csao. si, para cualesquiera dos cadenas w y x. Sean w una cadena y n ∈ N. w^(n) es igual a: w, si n = 0. w^(n-1), si |w| = 0 y n > 0. ε, si n > 0 y |w| > 0. Dados dos conjuntos A y B, y sea F ⊆ A x B. F es una funcion entre A y B. F es una relacion de equivalencia entre A y B. B es el conjunto final de la relacion F. Sea L = (0+1)* 100, las cadenas x = 01011 e y = 100 son distinguibles con respecto a L ya que. ∃z = 01 | xz ∉ L ∧ yz ∉ L. ∃z = 00 | xz ∈ L ∧ yz ∉ L. ∃z = 10 | xz ∈ L ∧ yz ∉ L. Sea M = (K,Σ,Γ,Δ,s,F) ∈ APND, (q,u,a) es una configuracion de bloqueo de M si. es terminal ∧ ∄ (q', u', α') ∈ K × Σ* × Γ* | (q, u, α) ⊢ (q', u', α'). |uα| > 0 ∧ ∄ (q', u', α') ∈ K × Σ* × Γ* | (q, u, α) ⊢ (q', u', α'). no es terminal ∧ ∃ (q', u', α') ∈ K × Σ* × Γ* | (q, u, α) ⊢ (q', u', α'). Cuando un AF alcanza una configuración terminal. queda bloqueado. acepta la cadena. podria transitar, pero solo si es no determinista. Si un lenguaje cumple la condición de bombeo regular entonces. puede representarse con una expresion regular. no podemos afirmar que es regular. no hay un AFD que lo represente. Sea G = (N, T, P, S) una GCL en FNG, entonces. ∀ α → β ∈ P, |α| = 1 ∧ |β| ≥ 0. ∀ α → β ∈ P, α ∈ N ∧ β ∈ {N ⋃ T}*. ∀ α → β ∈ P, α ∈ N* ∧ β ∈ T. Sea M = (K, Σ, Δ, s, F) ∈ AFND. Una configuración inicial de M es toda configuración. (f, w), con w ∈ Σ ∧ f ∈ F. (s, w), con w ∈ Σ^(+). (s, w), con w ∈ Σ*. Sea M un APND. Una computacion terminada de M puede estar bloqueada. Si acepta la cadena vacia entonces el estado inicial es tambien final. Si ninguna computacion de M altera el contenido de la pila entonces L(M) ∈ L.3. En un APND una configuracion. Es una terna perteneciente a K x Σ* x Γ*. Es una terna perteneciente a K x Σ^(+) x Γ^(+). Es una terna perteneciente a K x Σ*. Dados los lenguajes L1={a2nbn,n≥0} y L2={anb2n,n≥0}, ¿cuál es el reconocedor más sencillo (según la jerarquía de Chomsky) para L1∩L2?. Un APND. Un AFD. Una máquina de Turing. ¿Cuál de estos lenguajes NO es de tipo 3?. L={anbmcn,n>5,m>0}. L={anbmcn,n=5,m>0}. L={anbmcn,n<5,m>0}. Dado un AFND M: L(M)={w∈Σ*∣δ*(q0,w)∈F}. L(M)={w∈Σ*∣δ*(q0,w)=F}. L(M)={w∈Σ*∣δ*(q0,w)∩F=∅}. Sea L un lenguaje regular, y que por lo tanto verifica el lema de bombeo regular. Sea uvw la cadena referenciada por dicho lema. Si |u|=0, entonces: |v|=n, siendo n el número de estados del AFD mínimo que reconoce L. w∈L. q0∈F. Sea AP un autómata de pila. Si se cumple que existe una constante k tal que el número de símbolos que puede haber simultáneamente en la pila no excede dicha constante k, entonces: El lenguaje reconocido por AP es L.2, pero no L.3. El lenguaje reconocido por AP es L.3. El lenguaje reconocido por AP puede ser L.3 ó L.2−L.3. Dado un alfabeto Σ, si un lenguaje L definido sobre Σ∗ es regular, entonces: Existe una partición ΠL sobre Σ* tal que ∥ΠL∥ es finito. Existe una partición ΠL sobre L tal que ∥ΠL∥ es finito. Toda partición ΠL sobre Σ* es de tamaño finito. ({A,B}, {0,1}, {A -> 0A|B, B -> 01|1}, A) justifica: Ambigua. no se. ni idea. Todo AFND tiene, al menos: APND equivalente. mmmm. nnnnn. L(AFND) – L(AFD) =. L(AFD) – L(AFND). gracias. denada. Si un lenguaje cumple CBCL, entonces. podría pertenecer a L.1 – L.2. podria no. podría mejor. |K| < |F| => L((K, Σ, δ, s, F)). ∉ AFD. ∈ AFD. ∈ APND. {S -> |A0, A -> |A0 | B, B -> CC, C -> 0D|, D -> 0D1 | ∈ }. 1^(k) 0^(i) 0^(j) 1^(j) 0^(k) | i,j, k> 0. 1^(k) 0^(i) 0^(j) 1^(j) 0^(k) | i,j, k< 0. 1^(k) 0^(j) 0^(i) 1^(j) 0^(k) | i,j, k< 0. L, K ∈ L.2 entonces: L ∩ K ∈ L.1. L U K ∈ L.1. L U K ∈ L.2. En una transición realizada por un AP. podria no consumir. Siempre consume. no consume. Dado un lenguaje de contexto libre L, representable mediante una gramatica en Forma Normal de Chomsky (FNC), su lenguaje complementario L_c. solo puede ser generado por una gramtica en FNC si L_c no contiene la cadena vacia. puede ser generado por una gramatica en FNC. en ningun caso puede ser generado por una gramatica en FNC. Dado un lenguaje L = {x^n, y^n : n ≥ 0}, el lema de bombeo para los lenguajes regulares permite demostrar que: L es un lenguaje regular. no es posible construir un automata finito que reconozca L. no es posible construir un automata con plila que reconozca L. Si L es un lenguaje de contexto libre, entonces no cumple el lema del bombeo para lenguajes regulares. falso. el lema del bombeo para lenguajes regulares no es aplicable a lenguajes de contexto libre. verdadero. |