ITEC 420: Computability Theory and Formal Languages
Prerequisite: ITEC 122
Credit Hours: (3)
A survey of attempts to model computation and formal language concepts.
Detailed Description of Content of Course
1. Finite automata and regular expressions
2. Nondeterministic automata
3. Regular and context free languages
4. Context free grammars
5. Pushdown automata
6. Turing Machines
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
Students who complete the course will be able to:
1. Demonstrate an ability to understand and apply mathematical concepts.
2. Describe, analyze, and design language generators and recognizers including context free grammars and both deterministic and non-deterministic finite automata, pushdown automata, and Turing machines.
3. Use a Pumping Lemma to prove that a language is not in a given class.
4. Explain the Church-Turing Thesis and its significance.
5. Describe example unsolvable problems and outline how a problem can be shown to be unsolvable.
6. Define the classes P, NP, NP-Complete and explain their significance.
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
Review and Approval
October 1, 1991 Updated for 1991-92 Ivan B. Liss, Chair
May 12, 1994 Reviewed for 1994-95 Edward G. Okie, Chair
Sept. 25, 2001 Updated John P. Helm, Chair
Revised: June 1, 2012