ITEC 420
COMPUTABILITY THEORY AND FORMAL LANGUAGES
- 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.
- 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.
- 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.
- 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.
- Assessment Measures
Assessment of student achievement is measured by written tests in class and by evaluation of problem solution sets completed outside of class.
- Other Course Information
None
- Review and Approval
DATE ACTION APPROVAL
Sept. 25, 2001 Updated John P. Helm, Chair |