Limbaje Formale si Automate · 2014 · Sesiune
- Profesor
- Lorina Negreanu
- Anul examenului
- 2014
- Sesiune
- Sesiune
- Serie
- CB
- Grupă
- 331-332
- Adăugat
- 3 februarie 2014 de anonim
1. Fie limbajul regulat L. Se defineste pref(L) = {x | yx apartine lui L}.
Cum este limbajul pref(L)? Demonstrati.
2. Se da limbajul regulat L si un alfabet sigma ce contine si simbolul 'a'.
Definim L' = {w din sigma star | exista w1, w2 din L astfel incat w = w1w2 si w contine cel putin 2 'a'}.
Cum este L'? Demonstrati.
3. Se dau 2 AFD-uri peste acelasi alfabet.
Cum se verifica daca exista un cuvant care nu este in niciunul dintre libmajele acceptate de cele 2 automate?
4. Fie gramatica G:
S -> A1B
A -> 0A | e
B -> 0B | 1B | e
a) Scrieti arborele de derivare pentru 000101
b) Scrieti APD-ul echivalent cu G
5. Descrieti ierarhia Chomsky
Cum este limbajul pref(L)? Demonstrati.
2. Se da limbajul regulat L si un alfabet sigma ce contine si simbolul 'a'.
Definim L' = {w din sigma star | exista w1, w2 din L astfel incat w = w1w2 si w contine cel putin 2 'a'}.
Cum este L'? Demonstrati.
3. Se dau 2 AFD-uri peste acelasi alfabet.
Cum se verifica daca exista un cuvant care nu este in niciunul dintre libmajele acceptate de cele 2 automate?
4. Fie gramatica G:
S -> A1B
A -> 0A | e
B -> 0B | 1B | e
a) Scrieti arborele de derivare pentru 000101
b) Scrieti APD-ul echivalent cu G
5. Descrieti ierarhia Chomsky