Final 40%.
Midterm 30%.
HW 30%. The homework is always due next Wednesday. The lowest score will be dropped, remaining scores will be averaged.
No late homeworks will be accepted!
Updates and homeworks will be posted here. Please check frequently.
Homework 1. Due Wednesday, Jan 18. 1.45, 1.49, 1.65; 3.1, 3.2, 3.3, 3.5, 3.7a-l, 3.9
Homework 2. Due Wednesday, Jan 25. 2.1, 2.2, 2.3, 2.12a-e
Homework 3. Due Wednesday, Feb 8. 2.10, 2.14,2.15,2.21a-d, 3.18, 3.19, 3.20, 3.21, 3.23.
Prove that the language of balanced parenthetical expressions (with "(", ")") cannot be accepted by a FA.
Homework 4. Due Wednesday, Feb 15. 3.38, 3.39, 3.41
Homework 5. Due Wednesday, Feb 22. 3.42, 3.49, 3.50, 3.51
Homework 6. Due Wednesday, Feb 29. 4.1a-d, 4.3, 4.10acd, 4.14, 4.27
Homework 7. Due Wednesday, March 7. 5.1ab,5.2, 5.5c, 5.12, 7.1 (note there is a typo there, it should be Fig. 7.5), 7.2, 7.4b
Approximate syllabus:
1. Introduction. Languages and computation: a high level view. Basic set operations. Mathematical induction.
2. Mathematical induction. Languages. Operations on languages.
3. Examples of languages. Regular languages and regular expressions.
4. Regular languages and regular expressions, continued. Finite state automata. Definition and examples.
5. Finite state automata. Extended transition function. Languages accepted by FA. Examples.
6. Constructing FA's to accept union, intersection and difference of languages.
7. Memory necessary to recognize languages. Distinguishable and pairwise distinguishable strings.
8. Languages that cannot be recognized by a FA. The pumping lemma.
9. Proof and applications of the pumping lemma.
10. Non-deterministic finite state machines.
11. NFA's. Converting regular expressions to NFA's.
12. Getting rid of non-determinism in NFA's. Proof of the first part of Kleene's theorem.
13. Kleene's theorem, part II. Converting FA's to regular expressions.
14. Context Free Grammars and Context Free Languages. Definitions and Examples.
15. Context Free Grammars and Context Free Languages. More examples. constructing CFG's for union, intersection and Kleene star of languages. Regular languages are context free.
16. Derivation trees and ambiguity.
17. Push-down automata. Definitions and examples.
18. Push-down automata.
19. Equivalence of CGF's and PDA's. Non-context-free languages. Pumping Lemma for PDA's.
20. Pumping Lemma for CFL's.
21. Turing machines. Definition and examples.
22. Turing machines for accepting languages and computation. Church-Turing thesis.
23. Universal and non-deterministic Turing machines. Recursively enumerable and recursive languages.
24. The halting problem.