Pre-requisite: CSE221
Alphabets, strings, and languages, Deterministic Finite Automata (DFA), Regular Languages, Regular Operations, Regular Language closure properties, Nondeterminism, Nondeterministic Finite Automata (NFA), Equivalence between DFA and NFA using the Subset Construction, Regular Expressions, Equivalence between Regular Expressions and Finite Automata, Converting Regular Expressions to NFA, Converting DFA into Regular Expressions using the State Elimination Method, Nonregular Languages, Pumping Lemma for Regular Languages, Context-Free Grammars (CFG) and Context-Free Languages (CFL), Parse Trees, Derivations, and Ambiguity, Chomsky Normal Form (CNF), the Cocke-Younger-Kasami (CYK) algorithm, Pushdown Automata (PDA) and its equivalence with CFGs
The objectives of this course are to
1. To explain the fundamentals of formal languages, grammars, and automata theory.
2. To provide knowledge of finite automata, regular expressions, and their equivalence in representing regular languages.
3. To provide knowledge of context-free grammars, pushdown automata, and their equivalence in representing context-free languages.
4. To give tools to show the limitations of various computational model
1. Introduction to Automata Theory, Languages, and Computation., John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman., 2006, 3rd, Prentice Hall
2. Introduction to the Theory of Computation, Michael Sipser, 2013, 3rd, Cengage
Text and Reference Books
| # | Description | Weight | Edit |
|---|
| Week | Lecture | CO Map |
|---|---|---|
|
Week 1 |
Lecture 1: Alphabets, Strings, Languages, and an Introduction to Deterministic Finite Automata (DFA) and Regular Languages. Lecture 2: More Examples of DFAs, the Regular Operations. |
N/A |
|
Week 2 |
Lecture 3: Problem-Solving on Designing DFAs. Lecture 4: Closure of Regular Languages Under Union: The Cross-Product Construction. |
N/A |
|
Week 3 |
Quiz 1 (DFAs and the Regular Operations) and Discussion. Lecture 5: Introduction to Nondeterministic Finite Automata (NFA), Converting NFAs to DFAs using the Subset Construction. |
N/A |
|
Week 4 |
Lecture 6: More Examples of NFAs, Closure of Regular Languages under the Regular Operations. Lecture 7: Introduction to Regular Expressions, Examples of Regular Expressions. |
N/A |
|
Week 5 |
Lecture 8: More Examples of Regular Expressions, Converting Regular Expressions to NFAs. Lecture 9: Converting DFAs to Regular Expressions using State Elimination. |
N/A |
|
Week 6 |
Quiz 2 (NFAs and Regular Expressions) and Discussion. Lecture 10: Nonregular Languages, the Pumping Lemma for Regular Languages. |
N/A |
|
Week 7 |
Midterm Week |
N/A |
|
Week 8 |
Lecture 11: Introduction to Context-Free Grammars (CFG) and Context-Free Languages (CFL). Lecture 12: CFGs continued, Parse Trees, Derivations, and Ambiguities. |
N/A |
|
Week 9 |
Lecture 13: Designing CFGs and Discussion. Quiz 3 (Context-Free Grammars) and Discussion. |
N/A |
|
Week 10 |
Lecture 14: Putting a Grammar into Chomsky Normal Form. Lecture 15: The Cocke-Younger-Kasami Algorithm. |
N/A |
|
Week 10 |
Lecture 16: Introduction to Pushdown Automata (PDA) Lecture 17: Designing PDAs and Examples. |
N/A |
|
Week 12 |
Quiz 4 (CNF, CYK, and PDAs) and Discussion. Lecture 18: Review |
N/A |
