Instructor: | Dr. Nelson L. Passos |
---|---|
Office: | Bolin Science Hall 126B |
Office phone: | 397-4129 |
E-mail: | nelson.passos@mwsu.edu |
Webpage: | cs.mwsu.edu/~passos |
Office Hours: | MF 1:30 - 4:00 pm |
TR 9:30 - 12:00 | |
Class Hours: | MWF 9:00 - BO 320 |
Study of the computability and complexity of computer problems, beginning with a review of mathematical concepts and the discussion of the automata theory, including finite automata, push-down automata and Turing machines.Course Description:
Automata and Formal Languages – An Introduction, by D. Kelley.Text book:
Tentative Agenda (revised):
January February March April May Grading
Jan 17 | Martin Luther King Holiday |
Jan 19 | Mathematical Foundations |
Jan 21 | Mathematical Foundations |
Jan 24 | Mathematical Foundations |
Jan 26 | Alphabets and Languages |
Jan 28 | Alphabets and Languages |
Jan 31 | Operations on Languages |
Feb 2 | SNOW STORM |
Feb 4 | SNOW STORM |
| Assignment # 1 |
Feb 7 | Finite Automata |
Feb 9 | SNOW STORM |
Feb 11 | Finite Automata |
| Assignment # 2 |
Feb 14 | Non Determinism |
Feb 16 | Equivalence of DFA and NFA |
Feb 18 | FA and Regular Expressions |
| Assignment # 2 |
Feb 21 | Pumping Lemma |
Feb 23 | Regular Grammars |
Feb 25 | Context Free Grammar (CFG) |
| Assignment # 3 |
Feb 28 | Chomsky Normal Form |
Mar 2 | Push Down Automata (PDA) |
Mar 4 | Push Down Automata (PDA) |
Mar 7 | Equivalence of PDA and CFG |
Mar 9 | Test # 1 |
Mar 11 | Pumping Lemma for CFG |
Mar 14 | Spring Break |
Mar 16 | Spring Break |
Mar 18 | Spring Break |
Mar 21 | Pumping Lemma for CFG |
Mar 23 | Turing Machine - basics |
Mar 25 | Turing Machine - basics |
| Assignment # 4 |
Mar 28 | Turing Machine |
Mar 30 | Variants of Turing Machines |
Apr 1 | Universal Turing Machines |
| Assignment # 5 |
Apr 4 | Languages and Turing Machines |
Apr 6 | Recursive Languages |
Apr 8 | Recursive Enumerable Languages |
| Assignment # 6 |
Apr 11 | Context Sensitive Languages |
Apr 13 | Context Sensitive Languages |
Apr 15 | Undecidable Problems |
Apr 18 | Halting Problem |
Apr 20 | Post’s Correspondence Problem |
Apr 22- | Easter Break |
Apr 25 | Post’s Correspondence Problem |
Apr 27 | Undecidability and CFG |
Apr 29- | Test # 2 |
May 2 | Complexity |
May 4 | Space Complexity |
May 6 | Time Complexity |
May 9 | Finals (Monday, 8:00 am) |
Tests: | 25 % (each) | |
---|---|---|
Final Exam: | 20 % | |
Assignments: | 25 % | |
Class Participation: | 5 % |
E-mail address:
nelson.passos@mwsu.edu