VIZAT

Decan Sef de catedra Prof. Univ. Dr. Rodica TRANDAFIR Conf. Univ. Dr. Rodica IOAN

FISA DISCIPLINEI

I. UNIVERSITATEA SPIRU HARET FACULTATEA MATEMATICA-INFORMATICA DOMENIUL DE LICENTA INFORMATICA SPECIALIZAREA INFORMATICA Anul universitar 2009 – 2010 Forma de invatamant ZI II. DENUMIRE DISCIPLINA LIMBAJE FORMALE SI AUTOMATE III. CODUL DISCIPLINEI MI2103 IV. Statut disciplina Obligatorie Optionala Facultativa (se marcheaza cu X) X V. Structura disciplinei (nr. ore) Semestrul (numar de la 1 la 6)

Curs (nr. ore/sapt. si total nr.ore/sem.)

Seminar (nr. ore/sapt. si total nr.ore/sem.)

Laborator (nr. ore/sapt. si total nr.ore/sem.)

Lucrari practice (nr. ore/sapt. si total nr.ore/sem.)

Proiecte (nr. ore/sapt. si total nr.ore/sem.)

3 2/28 2/28 - - - VI. (ETCS) Numar credite 6 VII. OBIECTIVELE DISCIPLINEI 1. Insusirea notiunilor de limbaj, limbaj regulat, expresie regulata, automat finit, automat

push-down, gramatica formala, gramatica liniara, gramatica independenta de context. 2. Evidentierea unor legaturi intre notiunile mentionate mai sus si utilitatea acestora in

scrierea compilatoarelor, procesarea limbajului natural si in studiul complexitatii calculului.

3. Realizarea unor programe in limbajul C (C++) pentru diferite reprezentari ale gramaticilor si automatelor.

4. Elaborarea unor algoritmi pentru transformarea de gramatici in gramatici echivalente (gramatici proprii, gramatici in forma normala Chomsky/Greibach).

5. Asigurarea compatibilitatii cu invatamantul de excelenta. VIII. CONTINUT TEMATIC 1. Limbaje, expresii regulate şi mecanisme generative fundamentale. Complexitatea

gramaticilor şi a limbajelor. 2. Mecanisme pentru recunoaşterea limbajelor regulate. Proiectarea optimală a automatelor. 3. Transformări asupra gramaticilor formale. Forme normale (Chomsky, Greibach). Lema

Bar-Hillel. 4. Automate pushdown, automate liniar mărginite şi maşini Turing. Puterea de acceptare a

claselor de automate. 5. ProprietăŃi de închidere ale limbajelor la principalele operaŃii cu limbaje (reuniune,

produs, Kleene, intersecŃie, substituŃii). 6. Introducere în analiza lexicală şi sintactică (algoritmi bottom-up / top-down, algoritmul

CYK). IX. TEME SEMINAR 1. Expresii si multimi regulate. 2. Gramatici, limbaj generat, complexitate sintactica. 3. Automate finite deterministe. Automate finite nedeterministe. Puterea de acceptare a

automatelor finite. 4. Optimizarea automatelor finite. Lema Bar-Hillel (de pompare). 5. Gramatici liniare si automate. 6. Gramatici independente de context. 7. Forme normale. 8. Automate pushdown si legatura cu gramaticile independente de context. 9. Masini Turing. 10. Proprietati de inchidere a familiei L3 la operatii. 11. Proprietati de inchidere a familiei L2 la operatii. 12. Alte proprietati de inchidere si probleme decidabile. 13. Analiza sintactica – 1 (Algoritmi bottom-up/top down). 14. Analiza sintactica – 2 (Algoritmul CYK). X. LUCRARI DE LABORATOR - XI. LUCRARI PRACTICE - XII. PROIECTE - XIII. Forma de evaluare (procent din nota finala) Examen Colocviu Verificare pe

parcurs Lucrari practice

Laborator Proiecte

- 70% - 30% - - XIV. Bibliografie Obligatorie minimala Suplimentara Facultativa 1. G. Albeanu, Limbaje

formale şi automate, Editura FRM, Bucureşti, 2009.

1. D. Ding-Zhu, K. Ker-I, Problem Solving in Automata, Languages, and Complexity, John Wiley & Sons, Inc., 2001.

2. J. E. Hopcroft, R. Motwani, J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2nd ed.,

1. A. V. Aho, M. S. Lam, R. Sethi şi J. D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd ed., Addison-Wesley, 2007.

2. A. Atanasiu, Al. Mateescu, Limbaje formale. Culegere de probleme, Ed. Univ. Bucureşti, 1990.

3. I. Atanasiu, D. Raiciu, R. Sion şi I. Mocanu, Limbaje formale şi automate. Îndrumar pentru aplicaŃii , MATRIX ROM, Bucureşti, 2002.

Addison-Wesley, 2001.

4. T. Jucan, S. Andrei, Limbaje formale şi teoria automatelor, Ed. Univ. "Al. Ioan Cuza", Iaşi, 2002.

5. A. P. Parkes, A Concise Introduction to Languages and Machines, Springer, 2008.

6. C. Popovici, S. Rudeanu, H. Georgescu, Bazele Informaticii, Vol. II, Ed. Univ. Bucureşti, 1991.

XV. Metode didactice (clasice/moderne) 1. Prelegerea - proiecŃie in amfiteatru, programe demonstrative. 2. Recomandarea, pentru studiul individual, a unor paragrafe din bibliografia indicată, în

vederea aprofundării sau extinderii cunoştinŃelor căpătate la curs/seminar. 3. Prezentarea unor exemple şi a unor probleme aplicative în cadrul cursului pentru sporirea

interesului cursantilor. 4. Evaluare folosind platforma Blackboard. Data Titular disciplina _____________________

Titlul didactic, Numele si prenumele

Lect. Dr. Dana VÎLCU

Semnatura _______________________