ITEC 420: Computability Theory and Formal Languages
Prerequisite: ITEC 322
Pre- or corequisites: ITEC 380
Credit Hours: (3)
Instructional Method: Three hours lecture.
A survey of attempts to model computation and formal language concepts.
Detailed Description of Content of Course
Topics include:
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
7. Undecidability
8. NP-Completeness
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.
Student Learning Outcomes
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 Measures
Assessment of student achievement is measured by written tests in class and by evaluation
of problem solution sets completed outside of class.
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
Revised June, 2023