Universitatea "Babes-Bolyai" Cluj-Napoca
Facultatea de Matematica si Informatica
FISA DISCIPLINEI

Limbaje formale
Cod
Semes-
trul
Ore: C+S+L
Credite
Tipul
Sectia
MI043
3
2+1+1
7
obligatorie
Informatică
Cadre didactice indrumatoare
Prof. Dr. MOLDOVAN Grigor, moldovan@cs.ubbcluj.ro
Prof. Dr. KASA Zoltan, kasa@cs.ubbcluj.ro
Lect. Dr. MOTOGNA Simona Claudia, motogna@cs.ubbcluj.ro
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
8. Metode de analiza lexicala si sintactica.
- Principalele etape ale compilarii
- Analiza sintactica descendenta si ascendenta. Gramatici de precedenta.
- Algoritmul lui Cocke-Younger-Kasami.
Bibliografie
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
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.