Limbaje Formale si Automate · 2015 · Sesiune
- Profesor
- Lorina Negreanu
- Anul examenului
- 2015
- Sesiune
- Sesiune
- Serie
- CA
- Grupă
- 331,332,333,334
- Adăugat
- 30 ianuarie 2015 de Alexandru Orlando
1. Fie L1 - LIC, L2 - nu este LIC. Cum este L1L2? Justificati.
2. Fie L = {(a^i)(b^j)(c^k)(d^m) | i + j + k + m = multiplu de 13}. Cum este L? Demonstrati.
3. 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.
4. Se da limbajul L = {w din {a,b,c}* | w are numar egal de a si b}. Scrieti regulile GIC pentru L.
5. Fie L = { x1#x2#x3....#xn | unde xi este din {a,b}* si pentru anumiti i, xi este palindrom (cel putin un palindrom)}. Ce fel de limbaj este L? Demonstrati. (Daca este intr-o anumita cateogrie, demonstrati de ce este acolo si justificati si de ce nu este in cadrul limbajului mai restrictiv).
6. L ={ro(M)ro(w) | M nu accepta w} este Turing acceptabil? Justificati.
- 6 subiecte: 50 de puncte;
- timp efectiv de lucru: 1 ora;
- nu a fost open-book.
2. Fie L = {(a^i)(b^j)(c^k)(d^m) | i + j + k + m = multiplu de 13}. Cum este L? Demonstrati.
3. 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.
4. Se da limbajul L = {w din {a,b,c}* | w are numar egal de a si b}. Scrieti regulile GIC pentru L.
5. Fie L = { x1#x2#x3....#xn | unde xi este din {a,b}* si pentru anumiti i, xi este palindrom (cel putin un palindrom)}. Ce fel de limbaj este L? Demonstrati. (Daca este intr-o anumita cateogrie, demonstrati de ce este acolo si justificati si de ce nu este in cadrul limbajului mai restrictiv).
6. L ={ro(M)ro(w) | M nu accepta w} este Turing acceptabil? Justificati.
- 6 subiecte: 50 de puncte;
- timp efectiv de lucru: 1 ora;
- nu a fost open-book.