Второй курс, посвященный теоретическому аспекту информатики.
Раздел в вики, посвященный этому курсу. Содержание курса:
- Deterministic finite automata: definition and examples
- Regular operations
- Examples of nondeterministic finite automata
- Definition of nondeterministic finite automata; equivalence of deterministic and nondeterministic finite automata
- Equivalence of deterministic and nondeterministic finite automata; closure under the regular operations
- Closure under the regular operations; regular expressions
- How to convert a regular expression to an NFA; how to convert a DFA to a regular expression
- How to convert a DFA to a regular expression; Pumping Lemma for regular languages
- Pumping Lemma for regular languages
- Context-free grammars
- Context-free grammars; every regular language is context-free
- Chomsky Normal Form; converting a context-free grammar to Chomsky Normal Form; pushdown automata
- Pushdown automata
- Converting a context-free grammar to a nondeterministic pushdown automaton; pumping lemma for context-free languages. Examples of languages that are not context-free.
- Turing machines; multi-tape Turing machines; equivalence of multi-tape Turing machines and single-tape Turing machines; what is an algorithm? Church-Turing Thesis.
- Definitions of a language being decidable and enumerable; Hilbert’s problem is enumerable; the languages A_DFA, A_NFA, and A_CFG are decidable; every context-free language is decidable; the language A_TM is enumerable.
- Countable sets; the sets N, Z, and Q are countable; the set of real numbers is not countable; there exist languages that are not enumerable.
- The Halting Problem is not decidable; the language A_TM is not decidable; language A is decidable if and only if both A and its complement are enumerable; the complement of A_TM is not enumerable; some more examples of languages that are not decidable (without proof); Post’s Correspondence Problem is not decidable (without proof).
Курс ведет Michel Smid