COSC 3340 - Intro to Automata and Computation

Dr. Rakesh Verma
Email: Find it here
Office 532 PGH, Ph: 743-3348
Office Hours for Fall 08: Tu., Th. 1.15-2pm (or by appt.)

» home

Welcome

Welcome to the course website for COSC 3340 - Intro to Automata and Computation.

Goals

To provide computer science students with a broad understanding of various models of computation, several different characterizations of the power of each model, and the relative power of the models. Students are taught what can and what cannot be computed even by idealized computing devices. They are exposed to essential computational paradigms in a rigorous way.

Topics

• Finite Automata and Regular languages
• Pushdown Automata and Context-free languages
• Turing Machines
• Church's thesis, Grammars, Universal Turing Machines
• The Halting Problem, Turing-Acceptability, Turing Decidability, and Unsolvable problems about Turing machines
• Cardinality of sets, Proof techniques, and basic defnitions

Grants

Partially funded by the NSF Grant, #0311407. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Who is this?

The Theory of Computer Science has been shaped by many great and influential people. Learn more about them by clicking on their picture. Let's see if you can identify some of them.