Si un AFD = {K, Σ, δ, s, F} sin estados inaccesibles reconoce el lenguaje vacío, entonces: ||Σ|| = 0 ||F|| = 0 ||F|| puede ser mayor que 0.
Sea L la longitud de una computación para una cadena w en un AFND. Entonces: L puede ser mayor que |w| L ≤ |w| L = |w| en cualquier caso.
Dado el alfabeto Σ = {0, 1}, ¿cuántos estados tiene el AF mínimo que reconoce el lenguaje L = {01, 10}? 1 2 3.
El lenguaje generado por una gramatica en Forma Normal de Chomsky: nunca contiene la cadena vacía siempre contiene la cadena vacía puede contener la cadena vacía.
¿Cuántos lenguajes hay sobre un alfabeto dado de modo que no haya cadenas sobre dicho alfabeto que sean distinguibles respecto a ese lenguaje? infinitos dos uno.
En un AFD, la función de transición δ se define como: δ: K x Σ* -> K δ: K x Σ -> K δ: K x Σ -> Σ.
Dado un alfabeto Σ y un lenguaje L ⊆ Σ*, con ||L|| = 3 y la cadena vacía no pertenece al lenguaje, y sea A el AF que reconoce L con el menor número de estados posibles ||K||. ||K|| = 1 ||K|| = 3 ||K|| = 2.
Dado un lenguaje regular que contiene la cadena vacía Para cualquier AFD que lo reconozca, su estado inicial es siempre final. Para cualquier AF que lo reconozca, su estado inicial es siempre final Para cualquier AFND que lo reconozca, su estado inicial es siempre final.
Dado un AFND que reconoce un lenguaje L, ¿Cuántas computaciones de aceptación (n) puede tener una cadena que pertenece a L? n = 1 n ≥ 1 n < ||L||.
Marca la afirmación verdadera: Toda gramática que es recursiva por la derecha e izquierda a la vez es ambigua. Toda gramática que es recursiva por la derecha e izquierda a la vez genera un lenguaje inherentemente ambiguo. Toda gramática que es recursiva por la derecha e izquierda a la vez no es regular.
Una gramática propia no puede generar el lenguaje vacío no puede ser recursiva no puede ser ambigua.
Opción 3 Opción 1 Opción 2.
Sea L un lenguaje regular y M el AFD mínimo que lo reconoce. Entonces: Para algunos lenguajes regulares puede haber AFNDs que lo reconocen con menos estados que sus respectivos AFDs mínimos. Cualquier AFND que reconozca L tiene como mínimo tantos estados como M Siempre existe un AFND que reconoce L que tiene menos estados que M.
(q0, baababaaa) |- (q1, ababaaa) |- (q3, babaaa) es una computación de un posible AFND es una computación completa es una computación de un posible AFD.
Sea el lenguaje L = {ε}. ¿Cuántos AFND aceptan dicho lenguaje? 2 1 Infinitos.
Marca la afirmación verdadera: Primera Segunda Tercera.
Si L₁ y L₂ son lenguajes de contexto libre, entonces también lo es: L₁∩L₁L₂ L₁*complemento(L₂) (L₁L₂∪L₁).
Marca la afirmación verdadera: L = Ø ⇒ L cumple la CBR y la CBCL L = Ø ⇒ L no cumple la CBR ni la CBCL L = Ø ⇒ L cumple la CBR pero no la CBCL.
Sea ΠL la partición que permite que un lenguaje L verifique el teorema de Myhill-Nerode, y sea F el conjunto de estados finales del AFD que reconoce L. Entonces se cumple que: ||F|| ≤ ||ΠL|| ||F|| ≠ ||ΠL|| ||F|| ≥ ||ΠL||.
Dado el AFND M, ¿qué lenguaje acepta? ab(ab)* (ab)*a(bb)* (ab)*.
Una GCL es ambigua si: existe una cadena del lenguaje generado por la gramática que es producto de más de un árbol de derivación. existe una cadena del lenguaje generado por la gramática que se obtiene de mas de una derivación. existe un árbol de derivación con dos productos distintos.
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.
Un lenguaje inherentemente ambiguia: es aquel generado por una gramática ambigua. es aquel que no puede ser generado por una gramática no ambigua. es aquel generado por una gramática inherentemente ambigua.
Marca la afirmación verdadera: Primera Segunda Tercera.
Una gramática es propia si no es recursiva izquierda y no tiene símbolos inútiles no es recursiva ni ambigua y no tiene símbolos inútiles no es recursiva y no tiene símbolos inútiles.
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.
Los autómatas con pila no deterministas no pueden alcanzar estados de bloqueo generan lenguajes de tipo 1 reconocen lenguajes de tipo 2.
Si un lenguaje cumple la condición de bombeo regular entonces no hay un AFD que lo represente puede representarse con una expresión regular no podemos afirmar que es regular.
Cuando, al menos, una cadena de un lenguaje generado por una GCL es el producto de más de un árbol de derivación, la cadena es del tipo wwᴿ la gramática es ambigua el lenguaje es regular.
Si una GCL es recursiva por la izquierda, entonces genera un lenguaje infinito existe una gramática regular equivalente existe una GCL equivalente que no es recursiva por la izquierda.
L = {0ⁿ1ⁿ} es un lenguaje de tipo 1 es un lenguaje regular cumple la CBR.
En la condición de bombeo regular, siendo x = uvw, se cumple que: |v| > 0 |uv| > n ∀m < 0 uvᵐw ∈ L.
Si M = ( {s,f}, {a,b}, {a,b}, {((s, aa, ε), (s,b)), ((s, εa, ε), (f,ε)), ((f, a, b), (f,ε))}, s, {f} ) entonces Primera Segunda Tercera.
Los lenguajes de contexto libre son cerrados para las operaciones de: unión, concatenación y estrella de Kleene unión, concatenación y complemento unión, concatenación , complemento, estrella de Kleene e intersección.
Marca la opción verdadera: Una gramática de tipo tres siempre está en FNC Una gramática recursiva por la izquierda puede estar en FNG Toda GRI esta en FNG.
Si GCL es ambigua si el lenguaje que genera tiene cardinal alef 0 es inherentemente ambiguo sus cadenas son producto de, al menos, un árbol de derivación.
Sea M un APND: Una computación terminada de M puede estar bloqueada SI ninguna computación de M altera el contenido de la pila entonces L(M) ∈ L.3 Si acepta la cadena vacía entonces el estado inicial es también final.
|
