Subiecte cazute la examen Limbaje formale si automate - 2010

1. Sa se stabileasca valoare de adevar a afiramtiei “ Fie M= ( Q, S, d, q0 , F ) un automat finit determinist. O stare q este inutila daca exista un cuvant w I S٭ a.Adevarat B.Fals

2. Sa se stabileasca valoare de adevar a afiramtiei “ Fie M= ( Q, S, d, q0 , F ) un automat finit

determinist. O stare q IQ este inaccesibila din q0 daca nu exista un cuvant w I S٭ asfel incat d(q0,w)=q a.Adevarat B.Fals

3. Sa se stabileasca valoare de adevar a afirmatiei: “Orice limbaj generat de o gramatica liniara este neregulat” a.Adevarat B.False

4. Sa stabileasca valoare de adevar a afirmatiei:”Fie G=(W,S,S,P) o gramatica liniara de dreapta.Atunci

exista automat finit nedeterminist M asfel incat L(M)≠L(G)”. a. Adevarat B. Fals

5. Sa se stabileasca valoare de adevar a afirmatieie: “Fie:G=(Ω,∑,S,P) o gramatica liniara la dreapta . Atunci exista un automat finit nedeterminist M asfel incat L(M)≠L(G) a. Adevarat B. Fals

6. Sa se stabileasca valoare de adevar a afirmatiei “Cuvant 001011 este acceptat de automatul finit

nedeterminist dat prin diagrama de mai jos”

a .Adevarat B. Fals

7. Sa se stabileasca valoare de adevar a afirmatiei: “Pentru fiecare G=(W,S,S,P) gramatica prorpie exista G1 in forma normala Chomsky echivalenta cu G”. a.Adevarat B.Fals

8. Fie gramatica independenta de context G pentru expresii aritmetice variabilele ao i b: E ::= E+E |E-E|E*E|E/E|(E)|a|b. Sa se indice valoare de adevar a afirmatiei:”Gramatica G este ambigua” A. Adevarat dar nu este sigur b. False

9. Sa se indice valoare de adevar a afirmatiei:”Expresia (∑∑),unde ∑ este un alfabet , corespunde limbajului format din cuvinte de orice lungime peste alfabetul ∑, inclusiv cuvantul vid”

a. Adevarat B .Fals

10. Sa se stabileasca valoare de adevar a afirmatie : "Daca L este un limbaj acceptat de un automat finit determinist atunci L este o multime regulata.". A.Adevarat b.Fals

11. Sa se stabileasca valoare de adevar a afiramtiei : “automate pushdown au acceasi putere de acceptare ca si automatele finite nedeterministe. “ A. Adevarat

b .False

12. Fie gramatica G = (S, A, B, C, D, a, b, c, S, S::=A|abcB, A::=C|D, B::=A|ab, C::=S). Sa se indice valoarea de adevar a afirmatiei: "Gramatica G este liniara la stanga".

a. Adevarat B. Fals

13. Sa se indice valoarea de adevar a afirmatiei: "Multimea numerelor naturale constituie un alfabet.". a.Adevarat B.Fals

14. Sa se indice valoarea de adevar L((ab)*) reprezinta multimea tuturor cuvintelor peste aflabetul a,b a.Adevarat b.Fals

15. ? L ((a+b)*) reprezinta multimea tuturor cuvintelor peste (a,b) ? A.Adevarat

b .Fals

16. ? Sa se stabileasca valoarea de adevar "O gramatica formala se numeste monotona daca este independeta de context si regulile sale V::=V au proprietatea |V|≤ |V| ( nu mai stiu daca e V sau v )

a) Adevarat B) Fals ( daca ar fi u::=V are proprietatea cu I u I ≤ I v I ar fi adevarata afirmatia )

17. B Lema de pompare afirma

Fie L un limbaj regulat oarecare.Exista atunci un numar natural nL asfel incat orice cuvant w € L cu |w| ≥ nL adminte o descompunere w= xyz care are proprietatile:

a) |xy| ≤ nL

b) |y| ≥ l c) xyjz € L pentru i ≥ 0 Sa se indice valoare de adevar a afirmatie: Limbajul descris de 0p | p – nr. prim nu este regulat” a) Adevarat B) Fals

18. Fie Σ = a, b. Ce puteţi spune despre echivalenţele de mai jos? a. (a*b)* ~ λ + (a + b)*b;

19. Nu pentru orice cuvant w apartinand L(G), unde G=(Ω, Σ, S, P) este o gramatica independenta de context, se poate stabili o relatie intre nr de derivari extreme stangi si nr de derivari extreme drepte. a) Adevarat B) Fals

20.

Se cunoste ca algoritmul de mai jos permite determinarea starilor utile ale unui automat finit determinist. Intrare: Q,S, q0,d,F Iesire: U' – multimea starilor utile SEQ 1 i:=0, U0 :=F; 2 do for a I S do for q I Q – Ui do if s(q,a) I Ui them Ui +1=Ui É(q); i=i+1; )while ( Ui -Ui -1

1Æ); 3. U'= Ui

END Sa se determine multimea Ui a starilor utile ala atomatului din figura urmatoare

a. 0,1,4 b.3 c.2,3,5

d.0,1,2,3,4,5,6posibil? O(mn)

21. Se cunoste ca algoritmul de mai jos perminte determinarea starilro accesibile ale uni aoutmat finit determinist

Intrare:Q,S,q0,d,F Iesire: Q' – Multimea starilor accesibile SEQ 1. i:=0, S0 :=qo; 2. do Si+1:=Si Éd(s,a) | s I Si, a I S ; i=i+1 while (Si-Si -1

1Æ); 3 Q' = Si END Sa se determine multimea S2 a starilor accesibile ale automatului din figura urmatoare:

a. 2,5,6 b. 0,1,2,4,5 c 0,1,2,4,5,6 d. 0,1,2,3,4,5,6

22. Sa se indentifice expresia regulata corespunzatoare limbajului acceptat de automatul finit nedeterminist din figura de mai jos ( in care e reprezinta cuvantul vid )

A. (0+1)*(01+10)0* B. (01)*(01+10)0* C. (0+1)*(010*+10*) Care din ele ? B sau C Mai sigur C ! D. (0+1)*(01+10+0*)

23. D Sa se determine gramatica independenta de context care genereaza limbajul regulat acceptat de

automatul finit determinist din figura de mai jos:

A. S::=0A|1B,A::=0A|1C, B::=1B|0C, C::=0C|1C| λ B. S::=00A|11B,0A::=0A|01C, B::=1B|10C, C::=0C|1C C. S::=0A|1B,A::=0A|1C, B::=1B|0C, C::=01C|λ d. S::=0A|1B,A::=0A|1C, B::=1B|0C, C::=0C|1C

24. Sa se determine limbajul acceptat de automatul pushdown dat prin diagrama de stare de mai jos reprezentand cuvantul vid

A ai bj ck | i,j,k ≥ 0,i=j sau i=k b ai bj ck | i,j,k > 0,i=j sau i=k …..? c ai bj ck | i,j,k ≥ 0,i=j=k d ai bj ck | i,j,k ≥ 0

25. D . Limbajul acceptat de AFN descris prin diagrama de tranzitie de mai jos (in care E reprezinta cuvantul vid) este descris de expresia regulata: 10p a. (ab + a)* b. (ab – a)* c. (a + b)* D. (ab + a)*aba

26. Fie gramatica independenta de context S::= XSX|R, R::=xTy|yTx,T::= XTX|X| λ, X::=x|y. Indicati

care dintre sirurile de mai jos face parte din limbajul generat de gramatica a. xxyx B. xx ? c. xyx ( nu este ) d.yxy

27. Solutia minimala a ecuatiei cu expresii regulate X = aX are forma X = a*b. Sa se determine solutia minimala a ecuatiei X = (0 + 1)X + 01*.

A. X=(01)* (0 + 1)* B. X=(0 + 1)* + 01* c. X=(0 + 1)* 01* D X=(0 – 1)* 0 + 1*

28. Expresia regulata care caracterizeaza multimea tuturor cuvintelor binare care contin cel putin doua zerouri consecutive .

a. (0+1)*(0+0)(0+1)* b. (0+1)*(0+0)*(0+1)* c. (01)*00(01)* D. (0+1)*00(0+1)* - posibil

29. Simplificand expresia regulata (a+b+aa)٭ se obtine expresia: A. ( a + ab)* - posibil b. ( a + b)* c. ( aa + b)* d. a*+ b*

30. Descrieţi în cuvinte limbajele corespunzătoare expresiilor regulate de mai jos. a. (01*)*0; b. (a + ba)*b*.

31. Care din multimile de ma jos defineste limbajul generat de gramatica S::= As|aAbb, A:: = λ,|aAbb A. ai b2i aj b2j|i ≥0,j≥1 - posibil b. ai b2i |i ≥0,j≥1 c. ai aj b2j|i ≥0,j≥1 d. aj bj |i ≥0,j≥1

32. A Care din gramaticile de ma jos genereaza limbajul 1n0n|n≥0 A. S::= 1S|S0| λ b . S::= 1S|S0|10 c . S::= 1S0| λ

d: S::= 1S0|10

33. Sa se determine gramatica independenta de context care sa genereze limbajul L = 0n12n|n≥0 a. S::= 0S1|1 B. S::= 0S11| λ - Posibil c. S::= 0S11|011 d. S::= 0S|S11| λ

34. B Sa se determine limbajul generat de gramatica G=(Ù, Ó, S, P), unde: Ù = S, A, Ó = a, b, c, d, P = S::=aSd|aAd, A::=bAc|bc.

A. L =ai bj ck dl |i=l,j=k,i,j,k,l >0 b. L =ai bj ck dl |i=l,j=k,i,j,k,l≥0 c. L =ai bj ck dl |i=j,k=l,i,j,k,l >0 d. L =ai bj ck dl |i=j,k=l,i,j,k,l≥0

35. A Fie gramatica independenta de context S::= XSX|R, R::= xTy|yTx, T::=XTX|X|λ, X::= x|y. Neterminalele gramaticii sunt:

A) S, X, R, T b) S, X, Y, T c) x, y, λ d) S, X, Y, T, x, y

36. Descrieţi în cuvinte limbajele corespunzătoare expresiilor regulate de mai jos.

a. (01*)*0; b. (a + ba)*b*.

37. ESTE RASPUNSUL A

38. C