CS3101 Theory of Formal Languages and Automata

This course will cover the Chomsky hierarchy of Formal Languages (regular sets, context-free languages, context-sensitive languages, and recursively enumerable languages) and the types of grammars and automata associated with each class in the hierarchy. Emphasis is placed on the major results of the theory as they apply to language and compiler design. In addition, the major results involving the concept of in decidability are covered.

Prerequisite

CS3001

Lecture Hours

Lab Hours

Course Learning Outcomes

On completion of the course the student should be able to:

Recognize when to use weak versus strong induction.
Construct proofs by induction.
Describe the complexity hierarchy of the following: regular sets, context-free sets, recursive sets, non-recursive but recursively-enumerable (r.e.) sets, and non-recursively-enumerable sets.
Explain the declarative and operational characterization of each complexity class.
Show via a proof that a given problem belongs or does not belong to a given class.
Illustrate problems that demonstrate proper containment of the classes.
Create a proof that a problem is not recursive, r.e. but not recursive or not r.e.
Demonstrate reducing a problem to another problem.