Subiecte Mate Info (1)
1
1. Automate finite. Nota 6 - automatul finit nedetermnist si determinist: definitii - teorema de ehivalenta intre ele: enunt - teorema Myhill-Nerode: enunt cu toate conceptele care apar - unicitatea automatului minimal: enunt cu conceptele care apar La alegere 2 demonstratii din cele 3 de mai sus fiecare notata cu 2p. 2. Proprietati ale familiei limbajelor regulate Nota 6 - proprietati de inchidere: definitii si enunturi - proprietati de decizie: definitii si enunturi - lema de pompare: enunt La alegere 2 demonstratii de inchidere: 1p fiecare La alegere 1 demonstratie de decizie/lema de pompare: 2p 3. Gramatici si expresii regulate Nota 6 - gramatica regulata: definitie - expresii regulate: definitie - echivalenta gramatici regulate si automate finite: enunt - echivalenta expresii regulate si automate finite: enunt - teorema Kleene: enunt La alegere 2 demonstratii din cele 3 de mai sus fiecare notata cu 2p. 4. Gramatici independente de context si automate pushdown Nota 6 - automatul pushdown: definitie - moduri de acceptare - echivalenta modurilor de acceptare: enunt - echivalenta gramaticilor independente de context cu automatele pushdown La alegere 2 demonstratii din cele 3 de mai sus fiecare notata cu 2p. 5. Forma normala Chomsky si aplicatii Nota 6 - forma normala Chomsky: enunt - lema de pompare: enunt La alegere o demonstratie din cele 2 de mai sus notata cu 4p. 6. Proprietati de inchidere pe familia lmbajelor independente de context Nota 6 - definitia tuturor operatiilor de inchidere invatate - enuntul rezultatelor de inchidere La alegere 2 demonstratii din cele de mai sus (una pentru inchidere si cealalta pentru neinchidere) fiecare notata cu 2p. 7. Probleme de decizie pe familia lmbajelor independente de context Nota 6 - problemele de decizie:enunturi - statutul acestora pe familia limbajelor independente de context: enunturi La alegere 2 dem. din rezultatele decidabile 2p fiecare, sau cea de nedecidabilitate 4p .
-
Upload
catalina-radu -
Category
Documents
-
view
20 -
download
0
description
ZC
Transcript of Subiecte Mate Info (1)
1. Automate finite.
Nota 6 - automatul finit nedetermnist si determinist: definitii - teorema de ehivalenta intre ele: enunt - teorema Myhill-Nerode: enunt cu toate conceptele care apar - unicitatea automatului minimal: enunt cu conceptele care apar
La alegere 2 demonstratii din cele 3 de mai sus fiecare notata cu 2p. 2. Proprietati ale familiei limbajelor regulate
Nota 6 - proprietati de inchidere: definitii si enunturi - proprietati de decizie: definitii si enunturi - lema de pompare: enunt
La alegere 2 demonstratii de inchidere: 1p fiecare
La alegere 1 demonstratie de decizie/lema de pompare: 2p 3. Gramatici si expresii regulate
Nota 6 - gramatica regulata: definitie - expresii regulate: definitie - echivalenta gramatici regulate si automate finite: enunt - echivalenta expresii regulate si automate finite: enunt - teorema Kleene: enunt
La alegere 2 demonstratii din cele 3 de mai sus fiecare notata cu 2p. 4. Gramatici independente de context si automate pushdown
Nota 6 - automatul pushdown: definitie - moduri de acceptare - echivalenta modurilor de acceptare: enunt - echivalenta gramaticilor independente de context cu automatele pushdown
La alegere 2 demonstratii din cele 3 de mai sus fiecare notata cu 2p. 5. Forma normala Chomsky si aplicatii
Nota 6 - forma normala Chomsky: enunt - lema de pompare: enunt
La alegere o demonstratie din cele 2 de mai sus notata cu 4p. 6. Proprietati de inchidere pe familia lmbajelor independente de context
Nota 6 - definitia tuturor operatiilor de inchidere invatate - enuntul rezultatelor de inchidere
La alegere 2 demonstratii din cele de mai sus (una pentru inchidere si cealalta pentru neinchidere) fiecare notata cu 2p.
7. Probleme de decizie pe familia lmbajelor independente de context
Nota 6 - problemele de decizie:enunturi - statutul acestora pe familia limbajelor independente de context: enunturi
La alegere 2 dem. din rezultatele decidabile 2p fiecare, sau cea de nedecidabilitate 4p .
