A second course on theoretical aspects of computer science.
- January 6: Overview
- January 8: Deterministic finite automata: definition and
examples
- January 13: Regular operations
- January 15: Examples of nondeterministic finite automata
- January 20: Definition of nondeterministic finite automata;
equivalence of deterministic and nondeterministic finite automata
- January 22: Equivalence of deterministic and nondeterministic finite
automata; closure under the regular operations
- January 27: Closure under the regular operations; regular
expressions
- January 29: How to convert a regular expression to an NFA;
how to convert a DFA to a regular expression
- February 3: How to convert a DFA to a regular expression;
Pumping Lemma for regular languages
- February 5: Pumping Lemma for regular languages
- February 10: Context-free grammars
- February 12: Context-free grammars; every regular language is
context-free
- February 17/19:
Winter break
- February 24: Chomsky Normal Form; converting a context-free grammar
to Chomsky Normal Form; pushdown automata
- February 26: Pushdown automata
- March 3:
Midterm, in class
- March 5: Converting a context-free grammar to a nondeterministic
pushdown automaton; pumping lemma for context-free
languages. Examples of languages that are not context-free.
- March 10: Turing machines; multi-tape Turing machines;
equivalence of multi-tape Turing machines and
single-tape Turing machines;
what is an algorithm? Church-Turing Thesis.
- March 12: 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.
- March 17: 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.
- March 19: 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).
- March 24:
- March 26:
- March 31:
- April 2:
Review
Профессор
Курс ведет Michel Smid |
|
