CSE350

CSE350

Theory of Computation: Honors

4

Radu Grosu

An introduction to the abstract notions encountered in machine computation. Topics include finite automata, regular expressions, and formal languages, with emphasis on regular and context-free grammars. Questions relating to what can and cannot be done by machines are covered by considering various models of computation, including Turing machines, recursive functions, universal machines, and probabilistic machines.

CSE 150

• Introduce abstract models of computation such as finite and push-down automata, and analyze their relative expressive power.
• Explore the connection between abstract machine models and formal languages, as specified by grammars.
• Enhance student’s awareness of both the power and inherent limitations of algorithmic computation via the study of Turing machines and/or other abstract computational models.
• Enable students to apply languages and automata to solve problems in applied computer science

Elements of the Theory of Computation, 2nd edition, Authors: Harry Lewis and Christos Papadimitriou Prentice Hall , New Jersey , Year: 1998,ISBN: 0-13-262478-8

Introduction to the Theory of Computation, Second Edition, by Michael Sipser, 2005, ISBN 0-534-95097-3

• Strings and languages (1 week)
• Regular languages, regular expressions and finite automata (3 weeks)
• Turing machines, unrestricted grammars, Church-Turing thesis (3 weeks)
• Introduction to recursion theory, universal Turing machine, halting problem, undecidability (3 weeks)
• Probabilistic computation (1 week)
• Applications to operating systems, programming languages, and other areas will be discussed throughout the semester

No large scale projects are required.

http://www.cs.sunysb.edu/~cse350