**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