Limbaje Formale si Automate · 2016 · Restanțe
- Profesor
- Lorina Negreanu
- Anul examenului
- 2016
- Sesiune
- Restanțe
- Serie
- CA+CB
- Adăugat
- 6 septembrie 2016 de anonim
1) Cum este limbajul L = {a^kb^k | k € N*, k <= 10000 }? Justificati.
2) Fie M1, M2 si M3 € AFD. Se poate determina algoritmic daca e € ( L (M1) (L(M2 ∩ L(M3))*. Daca este adevarat, atunci scrieti algoritmul. Altfel, demonstrati prin reducere la absurd ca nu se poate.
3) Construiti gramatica pentru limbajul L = {a^ib^jc^k | j = i+k }.
4) Demonstrati ca L = {0^i1^j | i ≠ j } nu este un limbaj regulat, folosind proprietatile de inchidere.
5) Fie Σ = { a,b }. Definim gramatica G: multimea tuturor limbajelor peste Σ care contin sirul "abba". Este G inchisa in raport cu urmatoarele operatii:complementare, reuniune, intersectie, concatenare sau Kleene Star ?
6) Cum este limbajul L = { ρ(M) | Ǝ w, |w| < 10, M accepta w } ?. Justificati.
2) Fie M1, M2 si M3 € AFD. Se poate determina algoritmic daca e € ( L (M1) (L(M2 ∩ L(M3))*. Daca este adevarat, atunci scrieti algoritmul. Altfel, demonstrati prin reducere la absurd ca nu se poate.
3) Construiti gramatica pentru limbajul L = {a^ib^jc^k | j = i+k }.
4) Demonstrati ca L = {0^i1^j | i ≠ j } nu este un limbaj regulat, folosind proprietatile de inchidere.
5) Fie Σ = { a,b }. Definim gramatica G: multimea tuturor limbajelor peste Σ care contin sirul "abba". Este G inchisa in raport cu urmatoarele operatii:complementare, reuniune, intersectie, concatenare sau Kleene Star ?
6) Cum este limbajul L = { ρ(M) | Ǝ w, |w| < 10, M accepta w } ?. Justificati.