Limbaje Formale Automate R

____

1. Daca L este un limbaj independent de context si R este un limbaj regulat atunci L ∩ R este un limbaj independent de context..

____

2. Indicati valoarea de adevar a afirmatiei: "Familia limbajelor regulate este cea mai mica familie de limbaje care contine limbajele finite si este inchisa la reuniune, produs (de limbaje) si la operatia *(inchiderea Kleene)".

____

3. Orice gramatica liniara la dreapta este echivalenta cu o gramatica de acelasi tip, dar cu reguli de forma: A ::= aB sau A ::= a, unde A, B ∈ , iar a ∈ { }.

____

4. Fie G o gramatica in care productiile sunt de forma A ::= Ba si A ::= a. Atunci exista o gramatica G’ echivalenta cu G pentru care productiile sunt de forma A ::= aB si A ::= a.

____

5. Fie L un limbaj acceptat de un automat finit nedeterminist. Este imposibil de construit un automat finit determinist, notat cu M, astfel incat L(M) = L.

____

6. Multimile regulate nu pot fi recunoscute de sisteme tranzitionale.

____

7. Fie G = ( , , S, P) o gramatica liniara la dreapta. Atunci exista un automat finit nedeterminist M astfel incat L(M) = L(G).

____

8. Un limbaj recunoscut de un sistem APD cu memoria pushdown vida nu poate fi recunoscut de un APD cu stari finale.

____

9. Familia limbajelor independente de context nu este inchisa la stelare (operatia * - inchiderea Kleene).

____ 10. Familia limbajelor independente de context este inchisa la substitutii. ____ 11. Indicati valoarea de adevar a propozitiei: "Daca L este un limbaj de tip i (i = 2 sau 3) atunci L+ este de tip i". c. Afirmatia este adevarata pentru i = 2 si este adevarata pentru i = 3 ____ 12. Fie G = ( , , S, P) o gramatica independenta de context si w∈ L(G), n numarul derivarilor stangi ale lui w din S, iar m numarul derivarilor drepte ale lui w din S. Atunci: e. n = m ____ 13. Fie L un limbaj acceptat de un automat finit determinist minimal cu n stari. Atunci L ≠ ∅ ⇔ exista w ∈ L astfel incat |w| < n; b. adevarat ____ 14. Fie

. Atunci:

c. L este limbaj infinit ____ 15. Fie afirmatia: “Daca

este un alfabet, atunci

* este multime numarabila”. Aceasta este:

b. Adevarata ____ 16. Fie = {a, b, c} si w = aabca. Care este numarul natural f(w) asociat cuvantului w prin aplicatia biunivoca dintre * si multimea numerelor naturale. d. 184 ____ 17. Fie un alfabet total ordonat. Ordinea de pe induce pe * ordinea lexicografica “<”. Atunci produsul (concatenarea) de cuvinte peste este monoton la dreapta. Afirmatia din urma este: a. Adevarata ____ 18. Se considera E = +(r+s)*s. Atunci E = b. (r*s)* ____ 19. Fie expresia regulata E = + rr*. Care din urmatoarele afirmatii este falsa d. E = r*r ____ 20. Fie expresia regulata E = ( +r)*. Care din urmatoarele afirmatii este falsa? d. *r ____ 21. Fie expresiile regulate A = (r*s)*, B = +(r+s)*s, C = (rs*)*, D = +r(r+s)*. Atunci b. A = B si C = D ____ 22. Fie expresia regulata E = (r+s)*. Care din urmatoarele afirmatii este falsa? a. E = r* + s* ____ 23. Fie expresia regulata E = b. r*

,

. Forma cea mai simpla a expresiei E este:

____ 24. Fie un alfabet nevid. Atunci card( *) < b. card( ) <

daca si numai daca:

____ 25. Fie G = ( , , S, P) gramatica in care = {A, B, S}, ::= bS | aA; A ::= bS; B::= aB | bS | a. Atunci: a. Var(G) = 3, Prod(G) = 3 si Simb(G) = 23

= {a, b} si care are urmatoarele reguli (productii): S

____ 26. Fie L un limbaj regulat si “s” un simbol arbitrar. Se considera afirmatia: “sL = {sw | w L} este un limbaj regulat”. Afirmatia este: a. Adevarata ____ 27. Fie gramatica G cu regulile S ::= 0A | 1S | 1, A ::= 0B | 1A, B ::= 0S | 1B | 0. Atunci L este: d. Multimea secventelor peste {0, 1} in care numarul simbolurilor 0 (zero) este multiplu de 3. ____ 28. Fie gramatica cu regulile: S ::= aA | aB, A ::= Sb; B::= b si L = L(G). Atunci: b. L este limbaj independent de context ____ 29. Un programator se prezinta la un interviu pentru a fi angajat in domeniul elaborarii interfetelor in limbaj natural. I se pune urmatoarea intrebare: “Fie G o gramatica regulata. Exista un algoritm care sa verifice daca limbajul generat de G este infinit?” Care este raspunsul corect pe care trebuie sa-l dea candidatul? a. DA ____ 30. Se considera mesajul: “Fie L1, L2 si L3 limbaje regulate. A cere sa se elaboreze un algoritm si sa scrie un nu are sens. Asa ceva este imposibil.” Din punct de program C/Java pentru a verifica daca vedere teoretic: a. Vorbitorul are dreptate b. Vorbitorul nu are dreptate ____ 31. Numai una din urmatoarele multimi poate fi recunoscuta de catre un sistem AFD. a. Multimea cuvintelor peste a, b cu un numar par de a si impar de b ____ 32. Se poate da o gramatica independenta de context G in care un cuvint w generat de G are mai multe derivari stangi decat drepte? b. Nu. ____ 33. Care din formele urmatoare (A fiind simbol util) nu confera unei gramatici independente de context proprietatea de ambiguitate? e. A ::= wB unde B este diferit de A, iar A nu apare prima pozitie a lui w. ____ 34. La un interviu pentru obtinerea unui loc de munca pentru proiectarea analizoarelor lexicale se pune urmatoarea intrebare: “Este necesar un algoritm pentru eliminarea ambiguitatii limbajelor regulate?” Care este raspunsul corect? b. Nu ____ 35. Se considera gramatica cu regulile S ::= if c then S else S | if c then S | a. Atunci: b. Gramatica G nu este ambigua ____ 36. Care este numarul minim de stari al unui AFD pentru a recunoaste limbajul {a, aa, aaa}. a. 1 ____ 37. Fie gramatica G cu productiile S ::= aAB | b, A ::= bSS | c, B ::= cSA | a. Cate cuvinte de lungime 36 contine L(G)? d. 0 (zero) ____ 38. Fie gramatica G cu regulile S ::= B | D, B ::= BCC | x, C ::= yx, D ::= xCyD | xy. Cate cuvinte din L(G) contin subsirul (yx)3, adica pe yxyxyx ca subsir? b. Nici unul ____ 39. Fie G o gramatica in forma normala Chomsky si w L(G) obtinut printr-o derivare de lungime 5. Care este lungimea lui w, |w|? a. 5 ____ 40. Fie o gramatica G in forma normala Chomsky si un cuvant w din L(G), de lungime 10. Care va fi lungimea unei derivari stangi pentru a genera w? a. 10 ____ 41. Fie L = {anbn | n>0} - {an | n>0}. Atunci L este: b. limbaj independent de context ____ 42. Fie L limbajul generat de gramatica cu regulile: S ::= A, A ::= xAx | y. Atunci L - {xnyxn | n 0} este: a. regulat

____ 43. Fie L = {anxbn | n 0} {anybn |n 0}. Atunci L este c. limbaj dependent de context ____ 44. Fie gramatica cu regulile: S ::= a | aAB, A ::= b | bBS, B ::= c | cSA. Atunci: c. G este ambigua ____ 45. Fie G1 gramatica cu regulile: S ::= AS | A, A ::= aB | bA si G2 gramatica avand regulile S ::= ABC; A ::= BB | ; B ::= CC | a; C ::= AA | b, L1 = L (G1) si L2 = L(G2). Atunci: a. ____ 46. Fie G1 gramatica ce are urmatoarele reguli P1: E ::= E + T | T, T ::= T*F | F; F ::= (E) | a si G2 gramatica cu regulile P2: E ::= E + T | T*F | (E) | a, T ::= T*F | (E) | a, F ::= (E) | a. Doi informaticieni se cearta privind echivalenta celor doua gramatici.Ce parere aveti? b. Gramaticile sunt echivalente. ____ 47. Fie L = {anbn | n 1} {an | n 1} {anbncn | n 1} . Atunci: c. L este limbaj dependent de context. ____ 48. Fie r si s expresii regulate. Care din urmatoarele afirmatii este adevarata: c. (rs+r)*r = r(sr+r)*s ____ 49. Fie A = 1 + 0(10)*(11+0) si B = (01)*(1+00). Atunci a. A si B sunt expresii regulate echivalente ____ 50. Prin n! notam produsul numerelor 1, 2, 3, ..., n. Se considera L = {an! | n 1}. Atunci: b. L nu poate fi recunoscut de un sistem tranzitional. ____ 51. Alegeti gramatica formala G = ( , , S, P) corecta pentru a genera limbajul L = {anbn | n 0}. b. = {S}, = {a, b}, P = {S ::= aSb, S ::= } n n ____ 52. Alegeti gramatica formala G = ( , , S, P) corecta pentru a genera limbajul L = {a b | n > 0}. c. = {S}, = {a, b}, P = {S ::= aSb, S ::= ab} ____ 53. Alegeti gramatica formala G = ( ,

, S, P) corecta pentru a genera limbajul L = {anbncmdm | n > 0, m

> 0}. d. ____ 54.

____ 55.

____ 56.

____ 57.

____ 58.

____ 59.

= {S, A, B}, = {a, b, c, d}, P = {S ::= AB, A ::= aAb, A ::= ab, B ::= cBd, B ::= cd} Alegeti gramatica formala G = ( , , S, P) corecta pentru a genera limbajul L = {anbncmdm | n 0 , m 0}. c. = {S, A, B}, = {a, b, c, d}, P = {S ::= AB, A ::= aAb, A ::= ab, B ::= cBd, B ::= cd, S ::= } Alegeti gramatica formala G = ( , , S, P) corecta pentru a genera limbajul L = {anbncmdm | n 1 , m 1} { }. c. = {S, A, B}, = {a, b, c, d}, P = {S ::= AB, A ::= aAb, A ::= ab, B ::= cBd, B ::= cd, S ::= } Alegeti gramatica formala G = ( , , S, P) corecta pentru a genera limbajul L = {anbmcmdn | n 1 , m 1}. b. = {S, A}, = {a, b, c, d}, P = {S ::= aSd, S ::= aAd, A ::= bAc, A ::= bc} Alegeti gramatica formala G = ( , , S, P) corecta pentru a genera limbajul L format din siruri de biti (literele 0 si 1} a caror lungime este multiplu de trei. a. = {S, A, B}, = {0, 1}, P = {S ::= 0A, S ::= 1A, S ::= , A ::= 0B, A ::= 1B, B ::= 0S, B :: = 1S} Alegeti gramatica formala G = ( , , S, P) corecta, dar cu numar minim de simboluri neterminale, pentru a genera limbajul L format din siruri de biti (literele 0 si 1} a caror lungime este multiplu de trei. Se considera gramatica G = ({S, A, B}, {a, b}, S, P), unde P = {S ::= bA | aB, A ::= bAA | aS | a, B::= aBB | bS | b}. G este in forma normala b. Greibach

____ 60. Unui automat pushdown ii corespunde o gramatica c. independenta de context n n ____ 61. Sa se studieze natura limbajului L = {a b | n 1}. b. independent de context

n

____ 62. Sa se studieze natura limbajului L = {a | n a. regulat

1}.

n m m n

____ 63. Sa se studieze natura limbajului L = {a b c d | n b. independent de context

1, m

1}.

____ 64. Sa se studieze natura limbajului L = {ab, aabb, aaabbb}. b. independent de context ____ 65. Sa se studieze natura limbajului L = {w | w

{0, 1}*, w contine un numar egal de simboluri 0 si 1,

adica N0(w) = N1(w)}. b. independent de context ____ 66. Sa se studieze natura limbajului L = {w | w {0, 1}*, w nu contine subsirul 011}. b. independent de context m n ____ 67. Sa se studieze natura limbajului L = {x y | n < m sau 2*m < n, n, m > 0}. b. independent de context m n p q ____ 68. Sa se studieze natura limbajului L = {a b c d | m + n = p + q, m, n, p, q 0}. b. independent de context m n

____ 69. Sa se studieze natura limbajului L = {a b | n < m< 2*n, n, m > 1}. c. dependent de context ____ 70. Sa se studieze natura limbajului L = {w {a, b}* | w = Rasturnat(w)}. Notatie: daca w = abcd,

atunci Rasturnat(w) = dcba. a. regulat ____ 71. Sa se studieze natura limbajului L = { w c. dependent de context

{a, b}* | simbolul a apare de un numar par de ori}.

.

____ 72. Sa se studieze natura limbajului L = { w ∈ {a, b}* | simbolul a apare de doua ori mai des decat

simbolul b} b. independent de context

____ 73. Sa se studieze natura limbajului L = {anbncn | n 1}. c. dependent de context ____ 74. Sa se studieze natura limbajului L = {ambncmdn | m, n 1} c. dependent de context n n n ____ 75. Sa se studieze natura limbajului L = {a b c d | n 1}. c. dependent de context n n n ____ 76. Sa se verifice daca limbajul L = {a b c | n > 0} este independent de context. b. fals ____ 77. Sa se verifice daca limbajul L = {an | n = 2k, k>0} este independent de context. b. fals n n m

____ 78. Sa se verifice daca limbajul L = {a b c | n b. fals

m

____ 79. Sa se verifice daca limbajul L = {an | n = 10k, k a. Fals ____ 80. Sa se verifice daca limbajul L = {an | n = k2, k a. Fals n

n

____ 81. Sa se verifice daca limbajul L = {a (bc) | n b. Adevarat

n + n, n

0} este independent de context.

0} este independent de context. 0} este independent de context. 1} este independent de context.

____ 82. Sa se verifice daca limbajul L = {w # Rasturnat(w) | w ∈ {a, b}+, iar #

{a, b}} este independent de context, unde Rasturnat(w) desemneaza oglinditul lui w, adica: Rasturnat(abcd) = dcba.

b. Adevarat n

k

____ 83. Sa se verifice daca limbajul L = {a | n = 10 , k 0} este de tip 3 (regulat). b. Fals ____ 84. Sa se verifice daca limbajul L = {an | n = k2, k 0} este de tip 3 (regulat). b. Fals

n

____ 85. Sa se verifice daca limbajul L = {a | n a. Adevarat

0} este de tip 3 (regulat).

____ 86. Sa se verifice daca limbajul L = {ap | p numar prim} nu este de tip 3 (regulat). a. Adevarat ____ 87. Sa se verifice daca limbajul L = {ambn | m si n relativ prime, adica cmmdc(m, n) =1} nu este de tip 3

(regulat). b. Adevarat ____ 88. Se considera limbajul format din toate cuvintele peste {a, b} care incep cu b si dupa care urmeaza 0,

1, 2 sau mai multe simboluri a. Alegeti expresia regulata corespunzatoare: d. ba* ____ 89. Se considera limbajul format din toate cuvintele peste {a, b} care contin simbolul b exact de doua ori. Alegeti expresia regulata corespunzatoare: a. a*ba*ba* ____ 90. Se considera limbajul format din toate cuvintele peste {a, b}. Alegeti expresia regulata

corespunzatoare: b. (a+b)* ____ 91. Se considera limbajul format din toate cuvintele peste {a, b} care contin consecutiv doua simboluri a sau doua simboluri b. Alegeti expresia regulata corespunzatoare: d. (a+b)*(aa+bb)(a+b)* ____ 92. La un examen oral se afirma ca " Nu exista un algoritm care verifica daca limbajul recunoscut de un automat finit determinist este infinit”. Ce parere aveti? b. Fals ____ 93. Valoarea de adevar a propozitiei "Familia limbajelor regulate nu este închisă la reuniune" este: b. Fals ____ 94. Un coleg iti spune ca: "Familia limbajelor independente de context este închisă la intersecŃie". Care

este valoarea de adevar a afirmatiei lui? b. Fals ____ 95. Se considera afirmatia: "Familia limbajelor regulate este inchisa la intersectie". Aceasta este: a. Adevarata ____ 96. Fie afirmatia: "Un limbaj recunoscut de un sistem AFN este recunoscut şi de un sistem AFD".

Valoarea de adevar a acestei afirmatii este: a. Adevarat ____ 97. Se considera propozitia: "Un limbaj recunoscut de un automat pushdown cu stiva vida nu poate fi

recunoscut si de un automat pushdown cu stari finale." Aceasta este: b. Falsa ____ 98. Un limbaj recunoscut de un automat pushdown cu stari finale nu poate fi recunoscut de nici un

automat pushdown cu stiva vida. b. Nu sunt de acord ____ 99. Pentru orice gramatica independenta de context care genereaza un limbaj L, se poate construi un

automat pushdown care recunoaste limbajul L. b. Adevarat. ____ 100. Exista si limbaje recunoscute de automate pushdown care nu pot fi generate de gramatici

independente de context. a. Fals