Universitatea "Babeş-Bolyai" din Cluj-Napoca

Facultatea de Matematică şi Informatică
FISA DISCIPLINEI

Limbaje formale Formal languages
Cod
Semes-
trul
Ore: C+S+L
Credite
Tipul
Sectia
MI043
4
2+1+1
6
obligatorie
Informatică
(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.
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. 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.