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.
|
