| Credits: |
|
1 unit (4 credit hours) |
| Contact Hours: |
|
3 lecture |
| Instructor: |
|
Professor Ge Xia |
| Last Taught: |
|
Spring 2013 |
| Text Book: |
|
Introduction to Automata Theory, Languages and Computation, 3rd ed.
By Hopcroft, Motwani, and Ullman. (Addison-Wesley, 2006.) |
|
|
|
| Description: |
|
An introduction to the theoretical foundations of computer science and formal models of computation. Topics include formal languages, finite automata, computability, and undecidability. |
|
|
|
| Prerequisites: |
|
CS202 (Analysis of Algorithms) |
Specific Course Goals:
After successfully completing this course, the student will be able to:
- Understand the basic abstract machine types and the basic types of formal languages; understand the correspondence between the machine types and the languages.
- Understand the difference between computable and incomputable problems and tractable and intractable problems.
Student Outcomes:
| ABET/CAC Outcome 1 |
Analyze a complex computing problem and to apply principles of computing and other relevant disciplines to identify solutions. |
Topics covered:
- Finite Automata
- Deterministic Finite Automata
- Nondeterministic Finite Automata
- Finite Automata with Epsilon-Transitions
- Regular Expressions and Languages
- Regular Expressions and Their Relationship to Regular Languages
- Properties of Regular Languages
- Proving Regularity
- Closure Properties
- Decision Problems
- Automata Equivalence and Minimization
- Context-Free Grammars
- Parse Trees and Applications
- Language and Grammar Ambiguity
- Pushdown Automata
- PDA Languages
- PDA and CFG Equivalence
- Deterministic PDA
- Context-Free Languages
- Normal Forms
- Pumping-Lemma
- Closure Properties
- Decision Properties
- Turing Machines
- Definition and Preliminaries
- Machine Extensions
- The Restricted Machine
- Undecidability and undecidable problems
- P and NP Problem Classes