| 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. A.Atanasiu: Bazele informaticii. Univ. Bucuresti, 1987
2. J.E.Hopcroft, J.D.Ullman: Introduction to Automata Theory, Languages, and Computation. Addison-wesley Publishing Company, Inc., 1979 3. L.Livovschi, C.Popovici, H.Georgescu, N.Tandareanu: Bazele informaticii. Ed.Did.si Ped., Bucuresti, 1981. 4. G.Moldovan, V.Cioban, M.Lupea: Limbaje formale si automate. Culegere de probleme.Universitatea "Babes-Bolyai" Cluj-Napoca, 1996. 5. G.Orman: Limbaje formale. Ed. Tehnica, Bucuresti, 1982. 6. L-D.Serbanat: Limbaje de programare si compilatoare. Ed. Academiei, Bucuresti, 1987. |
| 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. |