Offered:
Pre-requisite: CSE221
Alphabets, strings, and languages, Deterministic Finite Automata (DFA), Regular Languages, the Regular Operations, Regular Language closure properties, Nondeterminism, Nondeterministic Finite Automata (NFA), Equivalence between DFA and NFA using 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, Turing Machines (TM), Turing-Recognizable and Turing-Decidable Languages, TM Variants, Undecidability, the Halting Problem, Reducibility.
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 the Theory of Computation, Michael Sipser, 2013, 3rd, Cengage
2. Introduction to Automata Theory, Languages, and Computation., John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman., 2006, 3rd, Prentice Hall
https://drive.google.com/drive/folders/1BWPisYhKz5lrLX3acom05QVeKINFbKmS?usp=sharing
# | 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 (CNF) and Cocke-Younger-Kasami (CYK) Algorithm. Lecture 15: Introduction to Pushdown Automata (PDA) |
N/A |
Week 10 |
Lecture 16: Designing PDAs and Examples. Lecture 17: Introduction to Turing Machines (TM), Turing Recognizable and Turing Decidable Languages. |
N/A |
Week 12 |
Lecture 18: Examples of TMs, Undecidability, Reducibility Quiz 4 (PDAs and Turing Machine) and Discussion. |
N/A |