Objectives and outcomes
Acquiring general and professional knowledge of the theory of algorithms, automata and languages. Students will acquire important concepts and knowledge of the theory of algorithms, automata and languages - about deterministic and non-deterministic finite automata, regular expressions and regular languages, properties of regular languages, context-free grammars and languages, automata, properties of context-free languages, Turing machine, classes of problems of polynomial and exponential complexity.
Lectures
Alphabets. Strings and languages over an alphabet. Formal grammars. Language of a grammar. Chomsky’s hierarchy of formal grammars. Deterministic finite automata. Transition function, extended transition function and language of an DFA. Nondeterministic finite automata. Extended transition function and language of an NFA. Equivalence of DFA and NFA, construction by subsets method.
Nondeterministic finite automata with empty strings (ɛ – NFA). Extended transition function and language of an ɛ – NFA. Equivalence of ɛ – NFA and DFA. Regular expressions. Finite automata and regular expressions. Equivalence of regular expressions and DFA in terms of formalism. Construction of a regular expression upon a DFA. Construction of a DFA upon a regular expression.
Use of regular expressions – lexical analysis. Regular languages. Pumping lemma. Equivalence and minimisation of automata. Minimisation of DFA. Context-free grammars. Derivations. Language determined by grammar. Derivation tree. Use of context-free grammars. Parsers. Pushdown automata. Acceptance by a final state. Acceptance by an empty stack. Equivalence of context-free
grammars and pushdown automata. Deterministic pushdown automata. Properties of context-free languages. Chomsky’s normal form for context-free grammars. Pumping lemma for context-free languages. Testing whether a given word belongs to a given context-free language. Turing machine. Multi-tape Turing machine. Nondeterministic Turing machine. Recursively enumerable and recursive languages. Classes P and NP. NP –complete problems. Proof of NP-completeness for CSAT and 3SAT.
Practical classes
In lectures, theory is supported by characteristic examples for easier understanding. Practical classes follow the lectures.