Universitatea "Babes-Bolyai" Cluj-Napoca
Facultatea de Matematica si Informatica
FISA DISCIPLINEI
| Limbaje formale |
trul |
|||||
| Cadre didactice indrumatoare |
|
| Obiective |
|
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. |
| Continut |
|
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 |
| Bibliografie |
|
1. A.V. AHO, D.J. ULLMAN - Principles of computer design, Addison-Wesley, 1978.
2. A.V. AHO, D.J. ULLMAN - The theory of parsing, translation and compiling, Prentice-Hall, Engl. Cliffs., N.J., 1972, 1973. 3. G. MOLDOVAN, V. CIOBAN, M. LUPEA - Limbaje formale si automate. Culegere de probleme, Univ. Babes-Bolyai, Cluj-Napoca, 1996, http://math.ubbcluj.ro/~infodist/alf/INDEX.HTM 4. CSÖRNYEI ZOLTÁN, Fordítási algoritmusok, Erdélyi Tankönyvtanács, Kolozsvár, 2000. 5. SIPSER, M., Introduction to the theory of computation, PWS Pulb. Co., 1997. 6. DEMETROVICS JÁNOS-DENEV, J.-PAVLOV, R., A számítástudomány matematikai alapjai, Nemzeti Tankönyvkiadó, Budapest, 1999. 7. L.D. SERBANATI - Limbaje de programare si compilatoare, Ed. Academiei RSR, 1987. 8. CSÖRNYEI ZOLTÁN, Bevezetés a fordítóprogramok elméletébe, I, II., ELTE, Budapest, 1996 9. D. GRIES - Compiler construction for digital computers,, John Wiley, New York, 1971. |
| Evaluare |
|
Pentru stabilirea notei finale se ia in considerare:
a) nota pentru activitatea de la laborator si seminar (50%); b) nota de la examenul scris (50%). 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. |