¿Qué conjunto de cadenas es totalmente aceptado por el autómata de la figura? {bbaba,ba,bba,ε} {ba,bba,bbb,ε} {baa,bbab,bbaba}.
((q0,1,1),(q1,0)) es una configuración de bloqueo de un autómata con pila es una configuración final de un autómata con pila especifica una transición de un autómata con pila.
Dado el AFND M = (K, Σ,Δ,s,K) ε ∈ L(M) |L(M)| !∈ N L(M) = Σ*.
La gramática ({A,B},{0,1},{A→0A|B,B→01|1},A) es ambigua está en forma normal de Chomsky está en forma normal de Greibach.
¿Qué expresión regular equivale a este AFND? 01*1(10)* 0(01)*+10* 11*+0(10)*.
¿Cuál de los siguientes vectores podría ser una transición de un APND con K = {q0,q1} y Σ = {a,b}? ((q0,a,ε),(q1,ε)) ((q0,ε),(q1,bba,ε)) ((q0,a,abb),(q1)).
¿Qué cadenas son indistiguibles respecto al lenguaje L = {0,1}*? todas las cadenas de L 0 y 1 01 y 11.
para todo par AFD M = (K, Σ,Δ,s,F) y M' = (K, Σ,Δ,s,K-F), se cumple L(M) = L(M') |L(M)| = |L(M')| negado(L(M')) = L(M).
El teorema de Myhill-Nerode afirma que un lenguaje L es regular sii el número de clases de equivalencia de la relación de indistiguibilidad es finito todo par de cadenas son distiguibles con respecto a un lenguaje L que cumpla el teorema L ∈ L.2 ↔ |ΠL| ∈ N.
Dado un lenguaje independiente del contexto cualquiera, su complemento podría no ser representable mediante autómatas con pila es también un lenguaje independiente del contexto es representable mediante un autómata finito.
L(DFA) - L(NFA) = L.3 L.2 - L.3 L(NFA) -L(DFA).
¿Qué cadena puede ser aceptada por ({q0,q1,q2},{0,1},{(q1,1,q0),(q1,1,q0),(q1,1,q2)},q0,{q2}? 0101 00 este autómata no acepta ninguna cadena.
Si un lenguaje L no cumple la condición de bombeo regular, entonces L ∈ L-2 -L.3 L !∈ L.3 L ∈ L.1.
La gramática ({A,B},{a,b},{A→aAa | aB, B → b},a) tiene dos árboles de derivación tiene infinitos árboles de derivación tiene 3 árboles de derivación.
¿Cuál de estas configuraciones de ({q0,q1},{|},Δ,q0,{q1}) es inicial? (q1,ε) (q0,|||) (q1,|||||).
¿Cuál de estas configuraciones de ({q0,q1},{|},Δ,q0,∅) es final? (q0,|||,ε) (q1,ε,ε) este autómata con pila no tiene configuraciones finales.
¿Cuál de estas configuraciones de ({q0,q1},{|},Δ,q0,{q1}) NO es final? (q0,ε) (q1,||||||) (q1,ε).
¿Cuál de estas transiciones puede ser realizada por ({q0},{0,1},{(q0,010,q0)},q0,{q0})? (q0,0100100100100) *(q0,ε) (q0,010010010)|-*(q0,101) (q0,0100100)|-*(q0,0).
¿Qué lenguaje representa este AFD? a(a+b)* {a,b}* a(a+b)(a+b)*.
Dado el siguiente AFD M = ({q0,q1,q2},{0,1},δ,q0,{q0,q1}), donde:
δ(q0,0)=q1
δ(q0,1)=q0
δ(q1,0)=q1
δ(q1,1)=q2
δ(q2,0)=q2
δ(q2,1)=q2
¿Qué lenguaje reconoce dicho autómata? Las cadenas binarias que contienen la subcadena 01 las candenas binarias que no contienen la subcadena 01 El lenguaje definido por la expresion regular 1*00*1(0+1)*.
Si un AFD M = (K, Σ,δ,s,F) sin estados inaccesibles reconoce el lenguaje vacío, entonces: || Σ || = 0 || F || = 0 || F || puede ser mayor que 0 .
El lenguaje generado por una gramática en forma normal de chomsky: Nunca contiene la cadena vacía siempre contiene la cadena vacia puede contener la cadena vacia.
¿Cuantos lenguajes hay sobre un alfabeto dado de modo que no haya cadenas sobre dicho alfabeto que sean distinguibles respecto a ese lenguaje? infinitos dos unos.
En un AFD, la función de transición se define como: δ: K xΣ* → K δ: K xΣ → K δ: K xΣ* → Σ.
Dado un lenguaje regular que contiene la cadena vacia:
para cualquier AFD que lo reconozca, su estado inicial siempre es final para cualquier AF que lo reconozca, su estado inicial siempre es final para cualquier AFND que lo reconozca, su estado inicial siempre es final.
Marca la afirmacion verdadera: toda gramatica que es recursiva por la derecha e izquierda a la vez es ambigua toda gramatica que es recursiva por la derecha e izquierda a la vez genera un lenguaje inherentemente ambiguo toda gramatica que es recursiva por la derecha e izquierda a la vez no es regular.
Una gramática propia... no puede generar el lenguaje vacio no puede ser recursiva no puede ser ambigua.
|
