Второй курс, посвященный теоретическому аспекту информатики.

Раздел в вики, посвященный этому курсу. Содержание курса:

• Overview
• 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