"Babes-Bolyai" University of Cluj-Napoca
Faculty of Mathematics and Computer Science

Formal languages
Code
Semes-
ter
Hours: C+S+L
Credits
Type
Section
MI043
3
2+1+1
7
compulsory
Informatică
Teaching Staff in Charge
Prof. MOLDOVAN Grigor, Ph.D., moldovan@cs.ubbcluj.ro
Prof. KASA Zoltan, Ph.D., kasa@cs.ubbcluj.ro
Lect. MOTOGNA Simona Claudia, Ph.D., motogna@cs.ubbcluj.ro
Aims
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.
Content
1. Grammars and languages, preliminary notions.
Languages and operations.
Grammars and languages generated by grammars.
The Chomsky hierarchy.
2. Finite automata.
Basic definitions and representions.
Languages accepted by finite automata.
Equivalence of deterministic and nondeterministic finite automata.
Minimization of finite automata.
3. Regular expressions.
Regular sets, regular expression. Equivalence to finite automata.
4. Regular languages.
Closure properties.
The pumping lemma for regular languages.
Equivalence to finite automata.
5. Context free grammars and languages.
Closure properties.
Derivation trees.
Simplification of context free grammars.
Chomsky and Greibach normal forms.
The pumping lemma for context free languages.
6. Pushdown automata.
Definitions. representation.
Languages accepted by pushdoawn automata and equivalence to context free languages.
7. Translation and translators.
8. Lexical and sintactical analysers.
Principle of compilers.
Ascending and descending analysers.
Precedence grammars.
References
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.
Assessment
Practical work and exam.