Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2023/2024
UPOZORNĚNÍ: Jsou dostupné studijní plány pro následující akademický rok.

Languages, Automats and Gramatics

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
B4B01JAG Z,ZK 6 2P+2S Czech
Garant předmětu:
Marie Demlová
Lecturer:
Marie Demlová
Tutor:
Jiří Demel, Marie Demlová
Supervisor:
Department of Mathematics
Synopsis:

Basic notions of the theory of finite automata and grammars: deterministic and non deterministic finite automata, languages accepted by finite automata, regular expressions. Grammars and languages generated by grammars with emphasis to context free grammars. A very brief introduction of Turing machines.

Requirements:

None

Syllabus of lectures:

1. Alphabet, words over an alphaber, concatenation of words, languages.

2. Deterministic finite automaton. Languages accepted by finite automata - regular languages.

3. Pumping Lemma and Nerode Theorem. Reduced finite automaton

4. Non deterministic finite automata. Subset construction. Properties of the class of regular languages.

5. Regular expressions. Relationship of regular languages and regular expressions. Kleen Theorem

6. Algorithmic approach to problems concering finite automata and regular languages. Introduction of grammars.

7. Chomsky hierarchy of languages generated by grammars. Regular grammars and retular languages. Context free grammars and context free languages.

8. Pumping Lemma for context free languages. Reduced context free grammars.

9. Pushdown automata, two types of languages accepted by pushdown automata.

10. Properties of the class of context free languages.

11. Deterministic pushdown automata and properties of languages accepted by them. The class

of deterministic languages, and the class of prefix-free languages.

12. A brief introduction to Turing machines.

Syllabus of tutorials:

1. Alphabet, words over an alphaber, concatenation of words, languages.

2. Deterministic finite automaton. Languages accepted by finite automata - regular languages.

3. Pumping Lemma and Nerode Theorem. Reduced finite automaton

4. Non deterministic finite automata. Subset construction. Properties of the class of regular languages.

5. Regular expressions. Relationship of regular languages and regular expressions. Kleen Theorem

6. Algorithmic approach to problems concering finite automata and regular languages. Introduction of grammars.

7. Chomsky hierarchy of languages generated by grammars. Regular grammars and retular languages. Context free grammars and context free languages.

8. Pumping Lemma for context free languages. Reduced context free grammars.

9. Pushdown automata, two types of languages accepted by pushdown automata.

10. Properties of the class of context free languages.

11. Deterministic pushdown automata and properties of languages accepted by them. The class

of deterministic languages, and the class of prefix-free languages.

12. A brief introduction to Turing machines.

Study Objective:

The aim of the course is to introduce students to the basics of the theory of formal languages. The main tools are finite automata and grammars.

Study materials:

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

Note:
Further information:
https://moodle.fel.cvut.cz/courses/B4B01JAG
Time-table for winter semester 2023/2024:
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
roomFS_KN:A-312
Demlová M.
14:30–16:00
(lecture parallel1)
Karlovo nám.
Posluchárna FS A:312 - záp.
roomKN:E-126
Demlová M.
16:15–17:45
(lecture parallel1
parallel nr.101)

Karlovo nám.
Trnkova posluchárna K5
roomKN:E-107
Demlová M.
14:30–16:00
(lecture parallel1)
Karlovo nám.
Zengerova posluchárna K1
Tue
Wed
Thu
roomKN:E-301
Demel J.
14:30–16:00
(lecture parallel1
parallel nr.102)

Karlovo nám.
Šrámkova posluchárna K9
roomKN:E-127
Demel J.
16:15–17:45
(lecture parallel1
parallel nr.103)

Karlovo nám.
Kotkova cvičebna K4
roomKN:E-112
Demel J.
14:30–16:00
(lecture parallel1
parallel nr.102)

Karlovo nám.
Cvičebna Vyčichlova
Fri
Time-table for summer semester 2023/2024:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2024-03-27
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet4681606.html