Limbaje Formale si Automate · 2014 · Sesiune
- Profesor
- Lorina Negreanu
- Anul examenului
- 2014
- Sesiune
- Sesiune
- Serie
- CA
- Grupă
- 331-334
- Adăugat
- 8 februarie 2014 de anonim
1. Se da limbajul L = {a^ib^j | 1<=i<=8 si 1<=j<=8}. Cum este L? Demonstrati.
2. Se da gramatica G peste alfabetul {a,b} descrisa de:
S -> SS | Sa | b
a) descrieti limbajul generat de gramatica G.
b) modificati gramatica G astfel incat sa se obtina o gramatica G' care descrie limbajul L(G') = {w | wR este in L(G)}. Extindeti pentru cazul general(cum obtinem limbajul reversed pentru orice gramatica data);
3. Se da limbajul L = {w din {a,b,c}* | w are numar egal de a,b si c}. Cum este L? Demonstrati.
4. Se da limbajul L care este Turing acceptat. Demonstrati ca limbajul prefix(L) este Turing acceptat.
prefix(L) = {w1 | exista w2 astfel incat w1w2 este in L}.
5. Se considera limbajul L, al carui complement este finit. Cum este limbajul L?(clasa cea mai restrictiva).
2. Se da gramatica G peste alfabetul {a,b} descrisa de:
S -> SS | Sa | b
a) descrieti limbajul generat de gramatica G.
b) modificati gramatica G astfel incat sa se obtina o gramatica G' care descrie limbajul L(G') = {w | wR este in L(G)}. Extindeti pentru cazul general(cum obtinem limbajul reversed pentru orice gramatica data);
3. Se da limbajul L = {w din {a,b,c}* | w are numar egal de a,b si c}. Cum este L? Demonstrati.
4. Se da limbajul L care este Turing acceptat. Demonstrati ca limbajul prefix(L) este Turing acceptat.
prefix(L) = {w1 | exista w2 astfel incat w1w2 este in L}.
5. Se considera limbajul L, al carui complement este finit. Cum este limbajul L?(clasa cea mai restrictiva).