"Babes-Bolyai" University of Cluj-Napoca
Faculty of Mathematics and Computer Science
| Formal languages |
ter |
||||||||||||||
| Teaching Staff in Charge |
|
| 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. 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. |
| Assessment |
|
Practical work and exam (50-50%). |