Languages, automata and grammars

Enrollement in the course requires an assessment of the following courses:

Discrete mathematics (A4B01DMA)

Lecturer:

Marie Demlová (gar.)

Tutor:

Marie Demlová (gar.), Jiří Demel

Supervisor:

Department of Mathematics

Synopsis:

The course covers basics of the theory of finite automata and grammars: deterministic and nondeterministic finite automata, characterization of the class of languages accepting by a finite automaton and description of such a language by a regular expression. Grammars and languages generated by a grammar, context-free grammars will be emphasized. The relation will be shown between context-free grammars and push down automata. Next topic is a Turing machine and the existence of non-decidable problems.

Requirements:

Discrete Mathematics

Syllabus of lectures:

1.Alphabet, strings over an alphabet, concatenation of words, language.

2.Deterministic finite automaton, state diagram.

3.Language accepted by a finite automaton, Nerode?s Theorem.

4.Nondeterministic finite automata.

5.Equivalence of deterministic and nondeterministic finite automata.

6.Regular expressions and regular languages, Kleen?s Theorem.

7.Properties of regular languages.

8.Grammars, regular grammars, context-free grammars.

9.Push down automata and their relation to context-free languages.

10.Properties of context-free languages, Pumping Lemma for context-free languages.

11.Algorithms for some problems concerning context-free languages.

12.Turing machines.

13.Non-decidable problems.

Syllabus of tutorials:

1.Alphabet, strings over an alphabet, concatenation of words, language.

2.Deterministic finite automaton, state diagram.

3.Language accepted by a finite automaton, Nerode?s Theorem.

4.Nondeterministic finite automata.

5.Equivalence of deterministic and nondeterministic finite automata.

6.Regular expressions and regular languages, Kleen?s Theorem.

7.Properties of regular languages.

8.Grammars, regular grammars, context-free grammars.

9.Push down automata and their relation to context-free languages.

10.Properties of context-free languages, Pumping Lemma for context-free languages.

11.Algorithms for some problems concerning context-free languages.

12.Turing machines.

13.Non-decidable problems.

Study Objective:

Study materials:

[1] J.E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, Second Edition, Addison-Wesley, 2001

Note:

Time-table for winter semester 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon	roomKN:E-301 Demlová M. 14:30–16:00 (lecture parallel1) Karlovo nám. Šrámkova posluchárna K9roomKN:A-320 Demlová M. 16:15–17:45 (lecture parallel1 parallel nr.101) Karlovo nám. Poslucharna Strojní A-320
Tue
Fri
Thu	roomKN:A-108 Demel J. 14:30–16:00 (lecture parallel1 parallel nr.102) Karlovo nám. Cvičebna -BUFETroomKN:A-108 Demel J. 16:15–17:45 (lecture parallel1 parallel nr.103) Karlovo nám. Cvičebna -BUFET
Fri

Time-table for summer semester 2011/2012:

Time-table is not available yet

The course is a part of the following study plans:

• Otevřená informatika - Počítačové systémy (compulsory course in the program)
• Otevřená informatika - Informatika a počítačové vědy (compulsory course in the program)
• Otevřená informatika - Softwarové systémy (compulsory course in the program)
• Otevřená informatika - před rozřazením do oborů (compulsory course in the program)