Limbaje Formale si Automate · 2011 · Sesiune
- Profesor
- Lorina Negreanu
- Anul examenului
- 2011
- Sesiune
- Sesiune
- Serie
- CA
- Grupă
- 334/335
- Adăugat
- 20 septembrie 2011 de Bogdan Ivanov
Subiecte ( 2.02.2011 ) 335CA + 334CA
1(?). Definim Maj(L1, L2, L3) = {multimea cuvintelor w care apar in cel putin din libajele L1, L2, L3 }. Demonstrati ca daca Maj(L1, L2, L3) este regulata daca L1, L2, L3
2. Daca L - LIC si S inclus in L . S neaparat LIC ? ( demonstratie )
3. L = {a^nb^n, c^m, n <= m <= 2n} . Demonstrati ca L != LIC .
4. L = {x1w1x2w2x3w3 ....xiwi+1} unde xi accepta siruri peste (c,d}* si wi accepta siruri de forma a^nb^n .
Descrieri GIC pentru L
Definiti APD-ul pentru gramatica de mai sus
5. Descrieti masina Turing care accepta siruri w peste {1, 2}* si lasa pe banda w' unde w' este urmatorul sir in ordine lexicografica
Precizari legate de subiect:
La 1 nu imi aduc foarte bine aminte enuntul .Poate ma corecteaza cineva . Era nevoie de demonstratie intr-un singur sens .
La 2 era nevoie practic doar de un contraexemplu ( gen L = a^nb^n si S = a^pb^p unde p e prim --> S nu e neaparat LIC)
3-ul era in This is Gold - pagina 27 ( unde coeficientul lui c era defapt i si nu m
La 4b) unde trebuia sa faci APD-ul, trebuia sa ii faci descrierea cu toate starile altfel nu primeai nimic . ( sau cel putin asa am fost avertizati inca de la inceputul examenului ).La începutul examenului am fost avertizați să nu facem un APD peste
șir, ci un APD din GIC-ul determinat la punctul a).
La 5 trebuia sa scrii in cuvinte cum arata masina Turing si cam ce operatii/stari faci .
Daca cumva am scris gresit la vreun exercitiu, va rog sa ma corecteze cineva de la 334/335.
Alte Precizari:
Examenul a avut 50 de minute.
Toate probleme au avut cate 10 puncte, exceptie facand problema 4 care a avut 20 de puncte ( 10 pentru fiecare subpunct ). Puteai acumula astfel in examen 60 de puncte dar era necesar 25 sa treci .
Corectarea mie mi s-ar parut foarte ok . ( De la noi nu cred ca a picat nimeni ) La noi a fost doar Diana la supraveghere . D-na profesoara a iesit din clasa vreo 30-40 de minute si nu a stat decat la inceput si la sfarsit . S-a putut vorbi cat de cat .
La corectare s-a tinut cont daca aveai peste 3 din seminar si se mai rotunjea la note ( de exemplu daca aveai nota X.1, X.2, X.3 se rotunjea la (X+1)). S-au luat note maricele .
--------------------------------------------------------------
Completari:
la 1. era :
"Definim Maj(L1, L2, L3) = {multimea cuvintelor w care apar in cel putin 2 din limbajele L1, L2, L3 }. Demonstrati ca daca Maj(L1, L2, L3) este regulata daca L1, L2, L3 sunt regulate"
la 2 a punctat chiar daca luai L regulat, nu LIC, desi la inceput zicea ca e gresit sa iei L regulat. Dar pentru siguranta, cand zice LIC, se refera la "clasa cea mai restrictiva e LIC".
4. i>0, n>0
5. era adunare in baza 2, dar cu 0 si 1 inlocuite de 1 si 2.
1(?). Definim Maj(L1, L2, L3) = {multimea cuvintelor w care apar in cel putin din libajele L1, L2, L3 }. Demonstrati ca daca Maj(L1, L2, L3) este regulata daca L1, L2, L3
2. Daca L - LIC si S inclus in L . S neaparat LIC ? ( demonstratie )
3. L = {a^nb^n, c^m, n <= m <= 2n} . Demonstrati ca L != LIC .
4. L = {x1w1x2w2x3w3 ....xiwi+1} unde xi accepta siruri peste (c,d}* si wi accepta siruri de forma a^nb^n .
Descrieri GIC pentru L
Definiti APD-ul pentru gramatica de mai sus
5. Descrieti masina Turing care accepta siruri w peste {1, 2}* si lasa pe banda w' unde w' este urmatorul sir in ordine lexicografica
Precizari legate de subiect:
La 1 nu imi aduc foarte bine aminte enuntul .Poate ma corecteaza cineva . Era nevoie de demonstratie intr-un singur sens .
La 2 era nevoie practic doar de un contraexemplu ( gen L = a^nb^n si S = a^pb^p unde p e prim --> S nu e neaparat LIC)
3-ul era in This is Gold - pagina 27 ( unde coeficientul lui c era defapt i si nu m
La 4b) unde trebuia sa faci APD-ul, trebuia sa ii faci descrierea cu toate starile altfel nu primeai nimic . ( sau cel putin asa am fost avertizati inca de la inceputul examenului ).La începutul examenului am fost avertizați să nu facem un APD peste
șir, ci un APD din GIC-ul determinat la punctul a).
La 5 trebuia sa scrii in cuvinte cum arata masina Turing si cam ce operatii/stari faci .
Daca cumva am scris gresit la vreun exercitiu, va rog sa ma corecteze cineva de la 334/335.
Alte Precizari:
Examenul a avut 50 de minute.
Toate probleme au avut cate 10 puncte, exceptie facand problema 4 care a avut 20 de puncte ( 10 pentru fiecare subpunct ). Puteai acumula astfel in examen 60 de puncte dar era necesar 25 sa treci .
Corectarea mie mi s-ar parut foarte ok . ( De la noi nu cred ca a picat nimeni ) La noi a fost doar Diana la supraveghere . D-na profesoara a iesit din clasa vreo 30-40 de minute si nu a stat decat la inceput si la sfarsit . S-a putut vorbi cat de cat .
La corectare s-a tinut cont daca aveai peste 3 din seminar si se mai rotunjea la note ( de exemplu daca aveai nota X.1, X.2, X.3 se rotunjea la (X+1)). S-au luat note maricele .
--------------------------------------------------------------
Completari:
la 1. era :
"Definim Maj(L1, L2, L3) = {multimea cuvintelor w care apar in cel putin 2 din limbajele L1, L2, L3 }. Demonstrati ca daca Maj(L1, L2, L3) este regulata daca L1, L2, L3 sunt regulate"
la 2 a punctat chiar daca luai L regulat, nu LIC, desi la inceput zicea ca e gresit sa iei L regulat. Dar pentru siguranta, cand zice LIC, se refera la "clasa cea mai restrictiva e LIC".
4. i>0, n>0
5. era adunare in baza 2, dar cu 0 si 1 inlocuite de 1 si 2.