| Instructor: | Tom Bennet | ||
| Office: | 109 Self Hall | ||
| Phone: | 925-3815 | ||
| Email: | bennet@mc.edu | ||
| Text: | Introduction to Languages and the Theory of Computation, by John C. Martin, McGraw-Hill, ISBN 0-07-040659-6 | ||
| Web Page: | http://www.mc.edu/~bennet/cs460. This will
grow during the semester. | ||
A study of languages, grammars, and machines at a theoretical level. Regular, context free, and context sensitive languages are covered, as well as finite state, push down, and Turing machines. The concept of decidability is also discussed.
This course covers the closely related topics of formal languages and automata. A formal language is simply a set of strings described in a formal way. An automaton is a theoretical computing machine also described formally. This course will cover several classes of formal language and automata, comparing their properties and expressive power. This body of knowledge provides the theoretical foundation to solve several practical problems in programming, particularly in building compilers. It also allows us to determine some basic limits on what can be computed.
Grading
The points for this course will be assigned as follows:
| Points, | Points, | ||||
|---|---|---|---|---|---|
| Activity | Undergrad. | Graduate | |||
| Written Homework | 150 | 150 | |||
| Regular exams (2 @ 100) | 200 | 200 | |||
| Graduate Problems, 3 @ 40 | 120 | ||||
| Comprehensive Final | 200 | 200 | |||
| TOTAL | 550 | 670 | |||
Course grades will be based on the percentage of the total points earned:
| Points, | Points, | ||||||
|---|---|---|---|---|---|---|---|
| Undergrad. | Graduate | Percent | Grade | ||||
| 495550 | 603670 | 90100% | A | ||||
| 440494 | 536602 | 8089% | B | ||||
| 385439 | 469535 | 7079% | C | ||||
| 302384 | 368468 | 55-69% | Undergraduate: D; Graduate: F | ||||
| 0301 | 0367 | 0-54% | F | ||||
Homework is assigned for each chapter. It is due a week after the chapter is covered in lecture, but not later than the final exam. Homework will be graded more on serious effort than correctness; exam problems will be graded on correctness.
Exams may be take-home, or have a take-home component.
The graduate problems are extra problems given with each regular exam and the final exam for graduate students only. Also, graduate students may have different exams, testing the same material, but in greater depth.
Schedule
Below are the topics to study for each chapter, and the homework assigned.
| Chapter | Assigned Problems | Homework | Challenging | ||||||
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1.3, 1.4, 1.9, 1.12, 1.13, 1.19, 1.20, 1.31 1.35 | 1.3, 1.19, 1.33 | |||||||
| 2 | 2.2, 2.3, 2.4, 2.5, 2.12, 2.15, 2.20, 2.21, 2.22, 2.25, 2.26 | 2.5, 2.15, 2.20(c), 2.21(b), 2.22(b)(ii) | 2.11, 2.12 | Be sure you understand inductive proof. It's not going away any time soon. | |||||
| 3 | 3.7, 3.9, 3.10, 3.12, 3.15 | 3.9 except parts (d), (e) and (h), 3.12 | 3.9(e), 3.9(h) | You should be comfortable with regular expressions and induction over the number of operators in an RE. | |||||
| 4 | 4.1, 4.2, 4.3, 4.5, 4.6, 4.12, 4.14, 4.15 | 4.2 except parts (d) and (i), 4.5, 4.14(a) | 4.2(d), 4.2(i) | Be comfortable with finite automata, and induction over the length of a series of transitions. | |||||
| 5 | 5.1, 5.2, 5.4, 5.5, 5.6, 5.8, 5.12, 5.17 | 5.6, 5.17(f), 5.17(g) | You should be able perform the algorithms for eliminating lambda transitions and non-determinism. | ||||||
| 6 | 6.1, 6.5, 6.6, 6.8 | 6.6(a), 6.8(a) | You should be able to perform the algorithms to convert between FA's and RE's. | ||||||
| 7, except Section 7.3 | 7.1, 7.2, 7.4, 7.10, 7.13, 7.14 | 7.4, 7.10(c), 7.13 | You should understand the relation IL and its equivalence classes, and be able to compute the minimum-state FA from a given one. | ||||||
| 8 | 8.1, 8.4 (a)(a), (a)(d), (c), 8.6, 8.7, 8.8(a), 8.10 | 8.1(a), 8.4(a)(a), 8.4(b) | 8.4(a)(c), 8.4(a)(d) 8.4(d) 8.8(a) | Understand and be able to use the Myhill-Nerode theorem and the Pumping Lemma for regular sets. | |||||
| 9 | 9.1, 9.7, 9.12, 9.14, 9.16, 9.18(a) | 9.7, 9.12 parts (a), (e), and (h) | Understand context-free grammars; be able to invent CFG's for specific languages and to prove things by induction over the number of steps in a derivation. | ||||||
| 10 | 10.1, 10.4, 10.7, 10.8 | 10.1, 10.8(a) | Understand ambiguity in CFG's. You are not responsible for Thm. 10.1 | ||||||
| 11 | 11.1, 11.2, 11.5, 11.6, 11.7 | 11.1, 11.5(c), 11.6(b), 11.7(c) | Understand and be able to perform the grammar transformations described in the chapter. | ||||||
| 12 | 12.1, 12.3, 12.4, 12.6, 12.8, 12.10, 12.12 | 12.4(c), 12.6(b), 12.8 | Understand the definition of a PDA, and be able to produce a PDA for a given language. | ||||||
| 13 | 13.1, 13.3, 13.4 | 13.1 | 13.3, 13.4 | Understand the proof of equivalence between CFG's and PDA's. | |||||
| 15 | 15.1, 15.2, 15.3, 15.7 | 15.1 | Understand and be able to use the CFL Pumping Lemma. | ||||||
| 16 | 16.1, 16.3, 16.5, 16.6, 16.9 | 16.3(a), 16.3(d), 16.5 | 16.9(c)16.9(h) | Be able to construct a TM for a given language, and understand the rules for combining TM's. | |||||
| 17 | 17.1, 17.5, 17.12 | 17.1, 17.12 | 17.5 | Understand the universal Turing Machine and its significance, and understand the variations on the TM. | |||||
| 18 | 18.1, 18.5, 18.7, 18.8, 18.9, 18.15, 18.17 | 18.1, 18.8, 18.9 | 18.5, 18.7, 18.15 | Understand recursive, recursively enumerable, and countable sets, and be able to show specific sets are or are not members of these classes. | |||||
| 19 | 19.1, 19.3, 19.8, 19.9, 19.13 | 19.3(a), 19.3(b), 19.13 | Understand un-restricted grammars and context-sensitive grammars, and be able to create them for a given language. | ||||||
| 20 | 20.1, 20.2, 20.3(a), 20.4, 20.9, 20.10, 20.11 | 20.2, 20.3(a) | Understand the idea of non-computable functions, and be able to prove functions non-computable. | ||||||
| 23 | 23.9, 23.14, 23.15 | 23.9, 23.14(a) | Understand the complexity class P and NP-completeness. | ||||||
| 24 | 24.6, 24.9 | 24.6 | Prove problems NP-complete. | ||||||
The schedule is optimistic. Chapters 18, 23 and 24 and most of 19 are considered expendable should time run short.
Attendance
Mississippi College class attendance policies as described on pp. 42 and 43 of the college catalog will be enforced. Absences may be excused for illness or other appropriate cause. Exams missed due to circumstances beyond the student's control may be made up at a mutually agreeable time and place. Adequate documentation of the cause of an absence may be required.
Academic Honesty
Mississippi College policies regarding the integrity of academic work described on pp. 45 and 46 of the college catalog will be enforced. Students are expected to do their own work. Penalties for violation range from low grades to dismissal. On programming assignments, this rule does not forbid a general discussion of approaches to be taken, or helping another student search for the cause of a specific bug. Broader assistance will generally be in violation of policy. If you have a question about applying this rule to your situation, simply ask your instructor. Real situations please; no hypotheticals.