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

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

  • 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

    9 Авг 2009 by freetonik

This website uses IntenseDebate comments, but they are not currently loaded because either your browser doesn't support JavaScript, or they didn't load fast enough.

Comment Form