Exercitii LFAC
1. Sa se gaseasca o gramatica pentru limbajul L = {anbn+mcmu, u ∊ {a,c}*, u are lungime
para, n ≥1, m ≥ 1}
2. Sa se gaseasca o gramatica de un tip cat mai mare pentru limbajul L = {anbmck, n ≥1, m
≥ 1, k = m+n }
3. Sa se gaseasca o gramatica de un tip cat mai mare pentru limbajul L = {anubnwdmcm, u ∊
{d,c}*, w ∊ {a,c}*, w contine cel putin 2 simboluri diferite n ≥1, m ≥ 1}
4. Sa se gaseasca o gramatica pentru limbajul L = {u ∊ {a,b}*, u contine un numar par de a}
5. Sa se gaseasca o gramatica pentru limbajul L = {am∗n1∗n2 ...∗nk ∗bm|k ≥ 1,ni numar
natural cu 4 cifre, 1 ≤ i ≤ k, m ≥ 2} ( ’*’ este terminal)
6. Gramatica de tip 3 pentru L = {++...+++w1++..++w2+..+++.....wn+++..+++++, wi ∈ {a, b,
c}+, wi contine cel putin un simbol a, n ≥ 0, exista cel putin un simbol + intre cuvinte}
7. Data urmatoarea gramatica: G = ({S,x}, {a,b,c}, S, P)
cu P:
S->axbxc
x->ax | a
x->bx | b
x->cx | c
Sa se descrie limbajul generat si sa se construiasca o gramatica de tip 3 echivalenta. Sa
se adauca apoi gramatica la forma normala
8. Construiti o gramatica de tip 2, care sa descrie multimea numerelor naturale pare cu cel
putin 3 cifre. Construiti si o gramatica de tip 3 echivalenta.
9. Construiti o gramatica de tip 2 care sa descrie multimea cuvintelor peste alfabetul {a, b},
in care numarul de a-uri este egal cu numarul de b-uri
10. L = {w1!w2! …..wk!, wi ∈ {a, b, c}*,wi contine sirul “ab”,1 ≤ i ≤ k, k ≥ 0}
Sa se obtina o gramatica de tip 3, folosind tehnicile de la proprietatile de
inchidere a familiei de limbaje L3 prezentate in curs (sa se scrie L ca iteratia
unui limbaj mai simplu )
11. Ce genereaza gramatica?
S → 1S
S → 0A
A → 1A
A → 0A
A→𝜀
Sa se construiasca o gramatica de tip 2 echivalenta, cu cel mult 5 reguli
12. Ce genereaza gramatica?
S → bS | aA
A → aA |a | bB |b
B → bB | aB |a |b
Sa se construiasca o gramatica de tip 2 echivalenta, cu cel mult 5 reguli
13. Gramatica care sa genereze structuri
sintactice de forma
Biblioteca
{
Carte {
Titlu: titlu
Autor:Nume autor
…………………….
Autor:Nume autor
},
………………………...
Carte {
Titlu: titlu
Autor:Nume autor
…………………………...
Autor:Nume autor
}
}
Terminalii sunt cu bold; titlul si numele autorului sunt siruri de 2 sau mai multe litere, prima litera
e o litera mare. Fiecare carte are un titlu si cel putin un autor
14. Fie gramatica:
G = ({S,A,B,C},S,{a,b,c},S,P) cu P:
S → BAaA
B →bBc|C
C→dC|𝜀
A →aA|bA| 𝜀
Sa se descrie limbajul generat si sa se aduca gramatica la forma normala Chomsky
15. Sa se construiasca gramatica in forma redusa echivalenta cu gramatica:
G = ({S,A,B,C,D},S,{a,b},S,P) cu P:
S → BAc|A
A →aA|bA
B →bBc|aCb
C→dC|ab
D→ aSd | b
16. Sa se construiasca un automat determinist pentru limbajul:
L = {amu, m>=1, u ∈ {a, b}* | u contine un numar par de a-uri si se termina cu sirul bb}
17. Sa se construiasca un automat determinist si o expresie regulata pentru limbajul:
L = { u ∈ {a, b}* | u nu contine ca subsiruri aa sau bb}
18. Sa se construiasca un automat determinist si o expresie regulata pentru limbajul:
L = { u ∈ {a, b}* | u contine cel mult 4 a-uri}
19. Sa se construiasca un automat determinist minimal si o expresie regulata pentru limbajul:
L = { u ∈ {a, b}* | u contine un numar de a-uri divizibil cu 3, u are lungime impara si se
termina cu b}
20. Simplificati expresia regulata: (a*|b*)*a*ba*. Sa se construiasca apoi un automat cu
epsilon tranzitii echivalent (A). Construiti apoi automatul determinist minimal echivalent cu
A’.
21. Simplificati expresiile regulate si apoi construiti automate nedeterministe (fara
epsilon-tranzitii) echivalente:
a) (01|1)*1*
b) 0*(0*1*|0*)
22. Construiti expresii regulate pentru limbajele:
a) L = {u ∈ {a, b,c}*, w contine cel putin 2 simboluri c si are lungime impara}
b) L = {u ∈ {a, b,c}*, fiecare simbol de pe pozitie impara este b sau c }
c) L = {multimea numerelor naturale cu cel putin 3 cifre pare si lungime impara}
d) L = {u ∈ {a, b,c}*, w contine numar par de a-uri si nu se termina cu bc}
23. Sa se construiasca un automat pushdown determinist care accepta L = {anwbn , w∈ {c,
d}+, n ≥ 1}
24. Sa se construiasca un automat pushdown determinist care accepta L = {anbmck, n ≥1, m
≥ 1, k = m+n }
25. Sa se construiasca un automat pushdown M cu o singura stare si fara stari finale care
accepta L = {(ab)ncn+2, n ≥ 0}