Worksheetslfa_iarna_1
Total questions: 20
Worksheet time: 5hrs 0mins
D4(4p). Definim urmatoarea operatie:
rep(L) = {u^nv^n | u,v in L, n>=0}
Care din urmatoarele afirmatii sunt adevarate?
rep(L(0*)) este un limbaj regulat.
daca L este un limbaj finit, rep(L) este un limbaj finit.
rep este o proprietate de inchidere pentru limbaje regulate.
pentru orice limbaj L, rep(L) nu este un limbaj regulat.
U5(1p). Care din urmatoarele perechi de stari NU pot fi distinse, din urmatorul AFD?
1 si 2
1 si 3
2 si 3
0 si 1
0 si 2
U3.(1p) Care din urmatoarele limbaje nu sunt independente de context?
{a^nb^m | n >= m >= 0} intersectat cu {a^nb^m | 0 <= n <= m}
{a^nb^nc^m | n,m >= 0} intersectat cu {a^nb^mc^m | n,m >= 0}
complementul limbajului {a^nb^m cu n>m>=0}
{w in {0,1} | #0(w) = #1(w)}
imbajul tuturor cuvintelor binare care codifica numere ce sunt puteri ale lui 2
M3(2p). Care din urmatoarele afirmatii sunt adevarate? (Prin "echivalente", intelegem automate care pot accepta aceleasi categorii de limbaje)
Un AFD este echivalent cu un AFN
Un APD este echivalent cu un AFD
Un APD care foloseste doar k celule ale stivei este echivalent cu un AFD
Un APD care foloseste doar k celule ale stivei este echivalent cu un AFN
Un APD care foloseste doar k celule ale stivei este echivalent cu un APD care foloseste doar k/2 celule ale stivei.
U9(1p). Care dintre urmatoarele expresii regulate accepta limbajul generat de gramatica:
S <- abS | Sba | bS | epsilon
(Mai jos, a? inseamna (a U epsilon))
(a?b)*(ba)*
(ba?)*(ba)*
(ab)*(ba)*
(ba)*(ab)*
(a U b)*
U1(1p). Care din urmatoarele limbaje sunt regulate?
L(A) intersectat cu L(N), unde A este un AFD, N este un AFN, amandoua avand cel mult 2 stari
{ww^R | w in {0,1} si |w| <= k, pentru un numar natural k fixat}
L(a*(b U epsilon)a*b*)
{a^n | n >= 0}
{a^nb^nc^n | n >= 0}
U6(1p). Daca L1 este un limbaj regulat iar L2 este un limbaj independent de context, care din urmatoarele afirmatii sunt intotdeauna adevarate?
L1 concatenat cu L2 este un limbaj regulat.
L1 concatenat cu L2 este un limbaj independent de context.
L1 intersectat cu L2 este un limbaj regulat.
L1 intersectat cu L2 este un limbaj independent de context.
L1 intersectat cu complementul lui L2 este un limbaj regulat.
U8(1p). Ce limbaj accepta PDA-ul din imagine?
{a^nb^mc^m | n,m >= 0}
{a^nb^mc^m | n,m > 0}
{a^nb^{n+m}c^m | n,m >= 0}
{a^nb^{n+m}c^m | n,m > 0}
{a^nb^nc^m | n,m >= 0}
M2(2p). Care din urmatoarele cuvinte pot fi folosite, alaturi de k=0, pentru a arata folosind Lema de Pompare ca limbajul {0^n1^{n+m}0^m | m,n >= 0} nu este regulat?
w_n = 0^n1^{n+m}0^m
w_n = 0^n1^n0^n
w_n = 0^n1^n
w_n = 0^n1^{2n}0^n
Nu exista un astfel de cuvant.
D3(4p). Care din urmatoarele gramatici sunt ambigue:
S <- aSbS | bSaS | epsilon
S <- aSbS | bSaS | ab | ba
S <- SS | a
U7(1p). Care din urmatoarele afirmatii sunt adevarate privitor la automatul A din imagine:
Cuvantul abba este acceptat.
Cuvantul abab este acceptat.
Automatul este unul finit determinist.
Numarul de stari finale este mai mare decat numarul de stari non-finale.
Limbajul L(bb*a) este inclus in L(A).
U10(1p). Fie A un automat finit determinist. Care afirmatii sunt adevarate?
Daca A nu contine sink states, atunci L(A) = Sigma*.
Daca A nu contine cicluri, atunci L(A) este finit.
Daca A nu contine stari finale, atunci L(A) = multimea vida.
Daca A contine o singura stare, atunci L(A) = {epsilon}
Daca A nu contine sink state, atunci A este un automat minimal.
M5(2p). Fie urmatoarea specificatie a unui lexer:
X : 0*;
Y : 1*;
Z : 0*1*;
W : (0 U 1)*;
Care din afirmatiile de mai jos sunt adevarate?
analiza lexicala a sirului 0001 va produce tokenii XY
analiza lexicala a sirului 0000 va produce tokenul Z
analiza lexicala a sirului 1000 va produce tokenul W
analiza lexicala a sirului 0101 va produce tokenii ZZ
M6(2p). Care din urmatoarele cuvinte pot fi folosite pentru a aplica lema de pompare, alaturi de k=0, pentru a arata ca limbajul {a^nb^{n+m}c^{m+k}d^k | n,m,k >= 0} nu este independent de context?
nu exista nici un astfel de cuvant.
w_n = a^nb^n
w_n = a^nb^{n+m}c^{m+k}d^k
w_n = a^{n/2}b^nc^nd^{n/2}
w_n = a^nb^{2n}c^{2n}d^n
M1(2p). Cate stari are automatul minimal care accepta limbajul:
L(((b U epsilon)a)*)
o stare
2 stari
3 stari
4 stari
5 stari
D1(4p). Care din urmatoarele limbaje sunt independente de context?
L1 intersectat cu L2, unde L1= {ww^R | w in {0,1}*} si L2 = {0^n1^m0^n | n,m >= 0}
L* unde L = {0^p | p este un numar prim}
L1 concatenat cu L2, unde L1= {a^nb^n | n >=0} si L2 = {b^na^n | n >= 0}
U4(1p). Care afirmatii sunt adevarate despre gramatica:
S <- aS | Sb | T
T <- epsilon | bS | Sa
este regulata.
este in Forma Normala Chomsky
genereaza {a^nb^n | n>= 0}
genereaza L(a*b*)
este independenta de context.
D2(4p). Numim SuperGex orice expresie regulata obisnuita, la care mai adaugam urmatoarele reguli de formare:
e ::= e{n} | !e | e \ e, avand urmatoarea semantica:
L(e{n}) = L(e)L(e) ... {n ori} ... L(e)
L(!e) = Sigma* \ L(e)
L(e \ e) = L(e) \ L(e')
Care din urmatoarele afirmatii sunt adevarate, daca E este un SuperGex?
L(E) este intotdeauna regulat.
L(E) este intotdeauna finit, daca E nu contine * (Kleene Star)
L(E) este intotdeauna independent de context.
L(E) nu este regulat.
U2(1p). Cate stari si tranzitii are AFD-ul obtinut din transformarea Regex-AFN-AFD, a expresiei regulate
(a U b)* ?
o stare
4 stari
3 stari
7 tranzitii
6 tranzitii
M4(2p). Care afirmatii sunt adevarate relativ la automatele din imagine:
L(A1) intersectat cu L(A2) este multimea vida
L(A1) este complementul lui L(A2)
L(A1) este reverse(L(A1))
L(A2) este reverse(L(A2))
L(A1) inclus in L(A2)
