Limbaje Formale si Automate · 2016 · Sesiune
- Profesor
- Lorina Negreanu
- Anul examenului
- 2016
- Sesiune
- Sesiune
- Serie
- CB
- Grupă
- 332+333+334
- Adăugat
- 4 februarie 2016 de anonim
1. Multimea limbajelor regulate peste alfabetul Σ={a} este finita? Justificati.
2. Care este alfabetul minim pentru ca urmatorul sir sa fie expresie regulata:
E = ( a ∪ b )*.(c.d ∪ Ø ).e* . Justificati.
3. Demonstrati ca limbajul L = { a^nb^nw | n >= 0, w ∈ {c,d}*, |w| = n } nu este independent de context utilizand proprietatile de inchidere.
4. Construiti o gramatica independenta de context pentru limbajul:
L = { w ∈ {0,1}* | w ≠ e, w incepe si termina cu acelasi simbol }.
Convertiti gramatica la automat pushdown.
5. Este posibil ca un limbaj nedecidabil sa fie NP-Complet ? Justificati.
6. Enuntati teorema care stabileste proprietatile algoritmice ale limbajelor independente de context.
2. Care este alfabetul minim pentru ca urmatorul sir sa fie expresie regulata:
E = ( a ∪ b )*.(c.d ∪ Ø ).e* . Justificati.
3. Demonstrati ca limbajul L = { a^nb^nw | n >= 0, w ∈ {c,d}*, |w| = n } nu este independent de context utilizand proprietatile de inchidere.
4. Construiti o gramatica independenta de context pentru limbajul:
L = { w ∈ {0,1}* | w ≠ e, w incepe si termina cu acelasi simbol }.
Convertiti gramatica la automat pushdown.
5. Este posibil ca un limbaj nedecidabil sa fie NP-Complet ? Justificati.
6. Enuntati teorema care stabileste proprietatile algoritmice ale limbajelor independente de context.