See also
**Orientation Materials**

**Instructor: **

Shunichi Toida, Emeritus Professor

Department of Computer Science, ODU

Office: Dragas 1100H

**Textbook:**

John C. Martin,

Introduction to Languages and the Theory of Computation,

4th ed., McGraw-Hill, Inc., New York, NY, 2011.

**Prerequisite: **

CS 381 (formerly CS 281) Introduction to Discrete Structures

This prerequisite is a must.

MATH 163 (Pre-Calculus II) or equivalent.

Calculus is preferred but not required.

**Grading:**

Homework | 20% | ||

Test x 1 | 40% | ||

Final Exam | 40% |

Test and exam are closed book. In the exam (but not for the test) you may use a one page cheat sheet.

Calculators/computers are NOT allowed.

Lying, cheating, plagiarism and failure to report such cases

all constitute violation of the Honor System.

**Office Hours: **

Wednesdays 2:30p.m. - 4:00p.m.

You may also walk in any other time or make an appointgment.

**Final Exam :** 1:00 - 3:30 a.m. Saturday, April 28, 2012 --- **Tentative**

**Course Objectives: **

The main objective of this course is to study the concept of computation and
limitations of computer and computation. By rigorously expressing the concept
of computation, one can characterize problems which are solvable using
computers, solvable but hard to solve or relatively easy to solve without
referring to any specific computer. In the process, important subjects
(practically as well as theoretically) such as finite automata, Turing
machines, regular languages and context-free languages are introduced and
studied. It is also an important objective of this course that we train
ourselves in logical thinking and problem solving. Finally it is also hoped
that we become able to read rigorous technical articles.

**Course Contents:**

First basic mathematics involving relations, functions, mathematical induction
and recursive definitions, which are given in Chapter 1, are reviewed.
Then in Chapters 2 and 3, one of the practically important classes of languages -
regular languages - is studied along with finite automata which process them.
Following that, another important class - context-free languages - and
push-down automata presented in Chapters 4 -6 are briefly looked at. The
theory of regular languages and context-free languages is heavily used in the
design of compilers for high level programming languages. Then the key
mathematical model for computation - Turing machine - presented in Chapter 7 is
studied. It is known that any computer is as powerful as a Turing machine. Also
it is conjectured (and generally accepted) that any so called "computation" is
a computation by a Turing machine with appropriate built-in rules. Finally,
using the concepts of computation and Turing machine, it is shown that there
are problems which can not be solved by any computer, which is discussed in
Chapter 9.