CS350: Automata and Formal Language Theory Fall 2005
Johnstone Course outline

Professor	Dr. J.K. Johnstone, CH125
Time	TTh 9:30-10:45am, 135 Education Building (new classroom)
TA	Daniel Chappell (danielcc@uab.edu)
Office Hours	Johnstone: M-F12-1; Chappell: M1:30-3, F3-5 (room TBA)
Prerequisites	CS250, CS302, and MA126 (with grades of C or better in all)
Textbook	J.E. Hopcroft, R. Motwani, and J.D. Ullman (2001)
	Introduction to Automata Theory, Languages, and Computation, Addison-Wesley.
Website	www.cis.uab.edu/cs350/

Additional References

• Harry Lewis and Christos Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1981.
• Michael Sipser, Introduction to the Theory of Computation. PWS Publishing, 1997.
• Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979.

Grading

 		 Homework (6) 		 40% 


Midterm 1 (Thursday, September 22) 		 15% 

		 Midterm 2 (Thursday, October 27) 		 15% 

		 Final     (Tuesday, Dec. 13, 8-10:30am) 		 30%

Homework	Chapters covered	Due date	Topic
HW1	1-2	9.6	DFA, NFA
HW2	2-3	9.13	NFA, DFA, RE translations
HW3	3-4	10.4	RE, pumping lemma 1, closure
HW4	5-6	10.18	CFG, parsing, PDA
HW5	6-7	11.8	CNF, GNF, pumping lemma 2
HW6	8-10	11.22	TM, NPC

I will drop your lowest mark on these 6 homeworks. Every homework is weighted equally. Homework is due in class, at the beginning of class. Late penalty is 10% per day; however, note that the homework must be handed in before a homework solution is handed back, which will be done within a week. (Typically homework is due on Tuesday and returned the next Tuesday.) Late homework should be handed in to the department office (Campbell 115), with a secretary's signature acknowledging time and date of receipt. Homeworks will be marked by the TA. I will mark all exams. Last day to withdraw with 'W': October 19, 2005.

Course Description

This is a course about the theory of computation, emphasizing formal models for hardware (automata) and software (formal languages). We shall also discuss the limits of each model and the limits of computation. Three classes of formal language will be studied: regular languages, context-free languages, and recursively enumerable languages, along with their associated hardware models.

Curriculum

1. Proof techniques (Chapter 1)
2. Regular languages (Chapters 2-4)
   1. Deterministic and nondeterministic finite automata.
   2. Regular expressions.
   3. Regular grammars.
   4. Properties of regular languages.
3. Context-free languages (Chapters 5-7)
   1. Context-free grammars.
   2. Simplification and normal forms for context-free grammars.
   3. Pushdown automata.
   4. Properties of context-free languages.
4. Recursively enumerable languages (Chapter 8)
   1. Turing machines.
   2. Church's thesis.
5. Computability and decidability (Chapters 9-10)
   1. Chomsky hierarchy.
   2. Undecidable problems.
   3. P vs. NP; NP-completeness.

Goals

1. Learning to think precisely and formally. For example, learning to prove things.
2. Learning to strip hardware and software down to its essentials, in the form of an automaton or grammar. This reveals the essence of hardware and software, and allows formal reasoning about them, such as compiler design, programming language design, search engines, and proofs of correctness for hardware.
3. Learning the limits of computation.

Honour code

All of the following are strictly forbidden:

• Any form of cooperation on exams, whether take-home or in-class.
• Any form of cooperation on homework, other than preliminary oral discussion at a high level (that is, definition of the problem). Homework is to be solved and written up alone and independently.
• Any coercion of other students to help on homework or exams (even if help is not forthcoming).

All references and/or websites used must be included in a bibliography. Care must be taken not to plagiarize.

Violations of any part of this honour code will result in a 0 on that exam/assignment/project, possible failure of the course, and possible forwarding of the case to the school ethics board, where a decision about expulsion from UAB is made.

Grading policy

In general, the marking scheme for this class will be as follows.

• A = 90-100
• B = 80-89
• C = 70-79
• D = 55-69

These standards may be adjusted for certain exams or homeworks, but any adjustment will be announced in class.

Attendance policy

You are expected to attend every class. If you must miss a class because of illness or other unavoidable reason, you are responsible for getting the notes and any assignments from a fellow student. Large gaps in attendance are not acceptable (e.g., if you must work during class hours, please drop the course).

Makeup policy

Midterm exams can be made up if missed due to illness, upon receipt of a doctor's note. The final exam cannot be made up. The final exam cannot be offered to students early (e.g., for Christmas travel).