Formal Langages and Automata | Faculty of Computer Science

Formal Languages and Automata

Course name

Formal Languages and Automata

Code

CS2103

Class	Computer Science, 2006 - 2009
Level	Undergraduate	Year	2	Semester	1	Status	Compulsory

Hours per week				Total hours per semester	Total hours of individual work	Credits	Evaluation type	Teaching language
C	S	L	Pr
2	2	0	0	56	94	5	M	ro

Taught by	Academic and scientific title, name
	Professor, PhD, Toader Jucan

Required courses

Objectives	The students who attend this course will have knowledge about grammars and automata. Also, they will obtain the skills to work with sequences of characters.
General thematics	Languages and generational grammars. Deterministic finite automata. Non-deterministic finite automata. State automata. Regular languages and type 3 languages. Transitional systems. Regular expressions. Closure properties for L₃ family. Non-deterministic pushdown automata. Closure properties for L₂ family. Normal forms for type 2 grammars. Derivation trees. Deterministic pushdown automata. Properties for L₀ and L₁ families of languages. Turing machines. Linear-bounded automata.
Seminary / Laboratory thematics	Generation of languages by grammars. Acceptance of languages by deterministic and non-deterministic finite automata. The minimal automaton. Examples of using the pumping theorems. Regular expressions. Languages accepted by pushdown automata. Languages accepted by Turing machines.
Teaching methods	The teaching of knowlegde will be made through exposure combined with conversation.

Bibliography

T. Jucan : Limbaje Formale şi Automate. Editura MatrixRom, Bucureşti, 1999.
T. Jucan şi Şt. Andrei : Limbaje Formale şi Teoria automatelor – Teorie şi Practică. Editura Universităţii „Al. I. Cuza”, Iaşi, 2002.
Gh. Grigoraş : Limbaje Formale şi Tehnici de compilare. Editura Universităţii „Al. I. Cuza”, Iaşi, 1985.
J.E. Hopcroft şi J.D. Ullman : Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishing Company, U.S.A., 1979.

Evaluation	conditions	Getting at least 3 points on each of the components of the final result.
	criterias
	modes	Mixed
	formula	0,5 (Control paper 1 + Control paper 2 + Seminary activity mark) / 3 + 0,5 Thesis mark