All the assigned course work can be found in the directory
/cs/course/2001
Course Work:
- Assignment 1, 7.5%;
deadline: February 1
- Assignment 2, 7.5%;
deadline: problems 1--4: February 10; problems 5--7: February 22
- Assignment 3, 7.5%;
deadline: March 17
- Assignment 4, 7.5%;
deadline: April 5
- Midterm, 30%;
date: February 22
- Final Exam, 40%;
date: April 14
Note: a student cannot receive a passing final grade
without receiving at least 13% on midterm and 20% on
the final exam.
The course TAs will be announced shortly.
Please note that you have only two weeks following the return of your course work to consult its marking.
Material covered so far
- Alphabets and Languages
- alphabets and strings
- operations on strings and sets of strings
- languages as sets of strings
- Finite Automata
- definition of deterministic finite automata (DFA)
- strings and the language accepted by a DFA
- regular languages; Pumping Lemma for Regular Languages
- non-deterministic finite automata (NFA): strings and the language accepted by a NFA
- equivalence of DFAs abd NFAs
- Regular Expressions
- regular expressions and languages defined by them
- operations on regular languages
- deriving finite automata from regular expressions
- equivalence of finite automata and regular expressions
- applications: search, lexical analysis
- Context Free Languages
- context free grammars (CFGs) and languages
- parsing (or derivation) trees, CFG ambiguity
- Chomsky Normal Form
- CFGs and programming languages
- (deterministic) pushdown automata
- applications: shift-reduce (or bottom-up) parsing
- Turing Machines
- deterministic Turing Machines (TMs)
- recursive and recursively enumerable languages
- TMs a scomputers of integer functions