CS 5104 Computability and Formal Languages

CS 5104: Computability and Formal Languages

Fall 2005

MWF 10:10--11:00am

McBryde 218

CRN 95413

Instructor: L. T. Watson, 630 McBryde, 231-7540, ltw@cs.vt.edu

Office Hours: 11:10--12:00 MWF, and by appointment.

Text: J. E. Savage, Models of Computation, XanEdu, Ann Arbor, Michigan, 1998. www.xanedu.com

Topics Covered:

Logic circuits, Boolean function normal forms, prefix computations, arithmetic, circuit complexity,

finite-state machines, random-access machines, Turing machines, simulation, pushdown automata,

regular and context-free languages, models of computability, reducibility and unsolvability,

recursive function theory, parallel computation, space-time tradeoffs.

Grading: FINAL GRADE will be the average of two in-class exams (50%), a final examination (25%),

and homework and class participation (25%).

Final Exam: 13:05--15:05, Friday, December 9, 2005.

Homework Assignments: All problems are from the text unless otherwise indicated.

References:

Clark and Cowell, Programs, Machines, and Computation, McGraw Hill, 1976.
D. I. A. Cohen, Introduction to Computer Theory, 2nd Ed., Wiley, 1997.
Davis, Sigal, and Weyuker, Computability, Complexity, and Languages, 2nd Ed., Academic Press, 1994.
Denning, Dennis, Qualitz, Machines, Languages, and Computation, Prentice-Hall, 1978.
Gill, Introduction to the Theory of Finite State Machines, McGraw-Hill, 1962.
Hopcroft, Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.
Kain, Automata Theory, Machines, and Languages, McGraw-Hill, 1972.
Kfoury, Moll, Arbib, A Programming Approach to Computability, Springer-Verlag, 1982.
Manna, Mathematical Theory of Computation, McGraw-Hill, 1974.
McNaughton, Elementary Computability, Formal Languages, and Automata, Prentice Hall, 1982.
Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, 1967.
B. M. Moret, The Theory of Computation, Addison-Wesley, 1998.
Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967.
R. G. Taylor, Models and Computation and Formal Languages, Oxford, 1998.