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

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

  • 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

Warning: Parameter 1 to id_generic_callback() expected to be a reference, value given in /home/users/f/freetonik/domains/css.freetonik.com/wp-content/plugins/intensedebate/intensedebate.php on line 911

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 19398091 bytes) in /home/users/f/freetonik/domains/css.freetonik.com/wp-includes/wp-db.php on line 450