| Limbaje formale | Formal languages |
trul |
|||||
(Computer Science) |
| Cadre didactice indrumatoare | Teaching Staff in Charge |
| Prof. Dr. KASA Zoltan, kasa@cs.ubbcluj.ro Prof. Dr. MOLDOVAN Grigor, moldovan@cs.ubbcluj.ro |
| Obiective | Aims |
|
1) Insusirea notiunilor de limbaj, limbaj regular, expresie regulara, automat finit, automat push-down etc.
2) Cunoasterea unor legaturi intre notiunile mentionate mai sus. 3)Realizarea unor programe in limbajul C, C++ pentru diferite reprezentari ale gramaticilor si automatelor. Elaborarea unor algoritmi pentru transformarea de gramatici in gramatici echivalente. |
Presentations of the elementary notions of language, regular language, regular expression, finite automaton, push-down automaton. Realizing computer programs in C and C++ for several representation of grammars and automata and grammars transformations. |
|
1. Gramatici si limbaje, notiuni generale.
- Limbaje si operatii cu limbaje - Gramatici, limbaj generat de o gramatica - Clasificarea Chomsky 2. Automate finite (AF). - Definitie, reprezentari - Limbaj acceptat de un AF - Echivalenta dintre AF deterministe si AF nedeterministe (AFN) - Minimizarea AF 3. Expresii regulare. - Multimi regulare, expresii regulare - Legatura dintre expresiile regulare si AFN 4. Gramatici si limbaje regulare. - Legatura dintre gramaticile regulare si AF - Proprietati de inchidere - Lema de pompare pentru limbaje regulare 5. Gramatici si limbaje independente de context. - Proprietati de inchidere - Arbori de derivare - Simplificarea gramaticilor independente de context - Formele normale Chomsky si Greibach - Lema de pompare 6. Automate push-down (APD) - Definitie, reprezentare - Limbaj acceptat de un APD si legatura cu limbajele independente de context 7. Translatare si translatoare. - Translator finit - Translator push-down 8. Metode de analiza lexicala si sintactica. - Principalele etape ale compilarii - Analiza sintactica descendenta si ascendenta. Gramatici de precedenta. - Algoritmul lui Cocke-Younger-Kasami. |
|
1. L.D. Serbanati - Limbaje de programare si compilatoare, Ed. Academiei RSR, 1987.
2. A.V. Aho, D.J. Ullman - Principles of computer design, Addison-Wesley, 1978. 3. A.V. Aho, D.J. Ullman - The theory of parsing, translation and compiling, Prentice-Hall, Engl. Cliffs., N.J., 1972, 1973. 4. D. Gries - Compiler construction for digital computers,, John Wiley, New York, 1971. 5. G. Moldovan, V. Cioban, M. Lupea - Limbaje formale si automate. Culegere de probleme, Univ. Babes-Bolyai, Cluj-Napoca, 1996. 6. Cioban, V., Lupea, M., Moldovan, G., Limbaje formale si automate. Culegere de probleme, http://math.ubbcluj.ro/~infodist/alf/INDEX.HTM 7. Csörnyei Zoltán, Bevezetés a fordítóprogramok elméletébe, I, II., ELTE, Budapest, 1996 8. Csörnyei Zoltán, Fordítási algoritmusok, Erdélyi Tankönyvtanács, Kolozsvár, 2000. 9. Demetrovics János-Denev, J.-Pavlov, R., A számítástudomány matematikai alapjai, Nemzeti Tankönyvkiadó, Budapest, 1999. 10. Sipser, M., Introduction to the theory of computation, PWS Pulb. Co., 1997. |
| Evaluare | Assessment |
|
Pentru stabilirea notei finale se ia in considerare:
a) nota pentru activitatea de la laborator; b) nota de la examenul scris. Activitatea de la laborator consta din intocmirea unui dosar cu lucrarile de laborator si realizarea unor programe in limbajul C++. Aprecierea activitatii de la laborator se bazeaza pe indeplinirea la timp a sarcinilor primite in cursul semestrului si printr-o verificare globala, in cadrul ultimului laborator, a dosarului si a programelor elaborate. Examenul scris consta din intrebari teoretice si probleme din materia parcursa la curs. Pentru promovarea examenului, cele trei note (laborator, teorie, problema) trebuie sa fie cel putin 5. |
Practical work and exam. |