|
Lecturer(s)
|
-
Brandejský Tomáš, doc. Ing. Dr.
-
Rak Josef, RNDr. Ph.D.
|
|
Course content
|
Lecture topics by week of the semester: 1. Introduction to language theory and grammar, history, basic concepts. 2. Regular expressions and regular sets. 3. Use of regular expressions, practical work with regular expressions. 4. Regular language (according to Chomsky's classification - type 3 language), use of regular expressions in defining the rules of a regular language. 5. Finite automaton as a tool for creating a lexical analyzer - scanner. 6. Context-free language (according to Chomsky's classification - type 2 language). Properties of context-free languages. 7. Derivation tree as a means for graphically expressing the structure of a sentence. Chomsky and Greibach's normal form. 8. Stack automaton and its relationship to context-free grammar. Use of a stack automaton in creating a parser. 9. Turing machines (TS). 10. Graphical representation of TS, modular construction, basic building blocks of TS. 11. Using TS as a language acceptor. Language accepted by TS. Modification of TS. Turing machines and type 0 languages. 12. Various problems and decidability bounds related to TS. 13. Algorithm complexity, polynomial commutability and intractable problems. The content of the exercises corresponds to the topics of the lectures.
|
|
Learning activities and teaching methods
|
Monologic (reading, lecture, briefing), Dialogic (discussion, interview, brainstorming), Skills training
- Home preparation for classes
- 20 hours per semester
- Contact teaching
- 52 hours per semester
- Term paper
- 45 hours per semester
- Preparation for an exam
- 33 hours per semester
|
|
Learning outcomes
|
The main goal of the subject is to familiarize students with theoretical informatics basis. The main skills are oriented to text analysis of programming language, compilers, Turing machines, decision problem and algorithm time complexity.
Passing the course enables basic information from the language theory, Turing machines, time complexity and the decision problem.
|
|
Prerequisites
|
There is expected basic knowledge of math, programming, algorithm development and data types.
|
|
Assessment methods and criteria
|
Oral examination, Home assignment evaluation
The condition for granting the credit is active participation in exercises and successful elaboration of semester works. The course ends with an exam. Active participation in exercises can be replaced by elaboration of tasks.
|
|
Recommended literature
|
-
JOHN E. HOPCROFT, Rajeev MOTWANI a JEFFREY D. ULLMAN. Introduction to automata theory, languages, and computation. 3. ed.. Pearson Addison: Wesley, 2014. ISBN 9781292039053.
-
LINZ, Peter. An introduction to formal languages and automata. Sixth edition.. Burlington, 2017. ISBN 9781284077247.
-
MAREŠ, Jan. Jazyky, gramatiky a automaty. 2. vyd.. Praha, 2011. ISBN 978-8001-04904-4.
|