Dr. Lou D'Alotto														
Syllabus for Formal Languages and Theory of Computation


REQUIRED TEXT:  Kimber, E., Smith, C., Theory of Computing - A Gentle Introduction, Prentice Hall, 2001.

GRADING CRITERIA:  Class exams, the final and theproblem sets will all count towards the final grade.  The final exam will consist of the entire semester's work and count for 1/3 of the final grade.  

COURSE OBJECTIVES: There are many computer programming languages that exist today.  This course will present the student with the theoretical development of languages.  Turing machines are the basic model of computation.  The concept, set forth by Alan Turing, provided the theoretical foundation to the modern day computer.  The development of algorithms rests on their computability.  An algorithm may exist but not complete in a reasonable (or finite) time.  In this course the student is expected to:

* Understand the meaning of computation and what it means to be computable.
* Understand the construction of programming languages.
* Further their understanding of logic.
* Synthesize the ability to develop simple languages that are acceptable by machines.


UNITS OF INSTRUCTION:


1. Review of Set Theory, Logic and Induction					(1 week)
2. Alphabets and Languages							(2 weeks)
   Alphabets, words grammars and languages
   Operations on strings
   Operations on Languages

3. Regular Languages								(3 weeks)
   Regular languages and regular expressions
   Deterministic Finite Automata (DFA)				
   Non-deterministic Finite Automata (NFA)
   Conversion from a NFA to DFA
   Nonregular Languages
   Language Acceptors							(Exam I)

4. Context-Free Languages							(3 weeks)
   Regular Grammars and Regular Languages
   Context-Free Grammars
   Parse Trees
   Pushdown Automata
   Languages that are not Context-Free
   Chomsky Normal Form

5. Turing Machines								(3 weeks)
   Definition of a Turing machine			
   Turing machines and language acceptors				(Exam II)	
   Constructions of Turing machines (Addition machine, Subtraction machine, Convert to ones complement machine and, Multiplication machine, Copy machine).
   Description of a Turing machine Simulator
   Universal Turing machines

6. Introduction to Computability and Uncomputability				(2 weeks)
   Decidability (Undecidable problems)
   The Turing Machine Halting Problem


BIBLIOGRAPHY:

1. Aho, A. V., Sethi, R., Ullman, J. D., Compilers: Principles, Techniques, and Tools, Addison-Wesley, 1985.
2. Aho, A. V., Ullman, J. D., Foundations of Computer Science (Principles of Computer Science Series), W H Freeman & Co., 1995.
3. Brookshear, G. Glenn, Theory of Computation: Formal Languages, Automata, and Complexity, Benjamin/Cummings, 1989.
4. Kelly, D., Automata and Formal Languages, Prentice Hall, 1995
5. Greenlaw, R., Hoover, H., J., Fundamentals of the Theory of Computation: Principles and Practice, AP Professional, 1998.
6. Harrison, M. A., Introduction to Formal Language Theory, Addison-Wesley, 1978.
7. Hopcroft, J. E., Motwani, R., Ullman, J. D., Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-Wesley, 2001.
8. Kinber, E., Smith, C., Theory of Computing, A Gentle Introduction, Prentice Hall, 2001.
9. Lewis and Papadimitriou, Elements of the Theory of Computation, 2nd ed. ,Prentice Hall, 1998.
10. Linz, P., An Introduction to Formal Languages and Automata, D. C. Heath, 1990.
11. Martin, J. C., Introduction to Languages and the Theory of Computation (McGraw-Hill Series in Computer Science), McGraw-Hill, 1997.
12. Moret, B., M., The Theory of Computation, Addison-Wesley, 1998.
13. Rayward-Smith, V. J., First Course in Formal Language Theory, Alfred Waller Ltd., 1983.
14. Rosen, K., Discrete Mathematics and Its Applications, 4th Edition, Random House, 1998.
15. Sipser, M., Introduction to the Theory of Computation, Pws Publishers, 1996.