Information Technology 420

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