ITEC 420
COMPUTABILITY THEORY AND FORMAL LANGUAGES

  1. Catalog Entry

ITEC 420. Computability Theory and Formal Languages
Three hours lecture (3).

Prerequisite: ITEC 122.

A survey of attempts to model computation and formal language theory. Student who have received credit for CPSC 420 may not receive credit for ITEC 420.

  1. Detailed Description of Content of Course

Topics covered:

1. Sets, functions, relations, strings, languages, concatenation
2. Finite automata
3. Regular expressions
4. Context-free grammars
5. Pushdown automata
6. Turing machines
7. Primitive and partial recursive functions
8. Recursively enumerable sets and degrees of unsolvability

The topics above are the standard topics included in textbooks on theoretical computer science as taught at most universities.

  1. Detailed Description of Conduct of Course

The course is a series of lectures which present the theory and illustrates it with examples and applications. Students also learn by solving and discussing numerous home work exercises, ranging from routine drill of basic concepts to difficult problems which require considerable ingenuity to solve.

  1. Goals and Objectives of the Course:

1. To introduce the student to the mathematical theories of computation and formal languages.
2. To improve the students' skill in reading and understanding higher mathematics.

  1. Assessment Measures

Assessment of student achievement is measured by written tests in class and by evaluation of problem solution sets completed outside of class.

  1. Other Course Information

None

  1. Review and Approval

DATE ACTION APPROVAL
Sept. 25, 2001 Updated John P. Helm, Chair