Automata and Computability
A. Course General Information:
Course Code: CSE331
Course Title: Automata and Computability
Credit Hours: 3
Contact Hours: 3
Category: Core
Prerequisites: CSE221
B. Course Catalog Description (Content):
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 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.
C. Course Objective:
The objectives of this course are to
01. To make students explore the fundamental capabilities and limitations of computer
algorithms, according to various computational models and measures.
02. To equip students with the prerequisite knowledge to write automated text processing
programs like lexers and parsers of compilers.
D. Course Outcomes (COs):
Upon successful completion of this course, students will be able to
Sl. CO Description
C Demonstrate mastery over regular languages, regular expressions, and
O deterministic finite automata.
1
C Demonstrate mastery over context-free languages, context-free grammars, and
O pushdown automata.
2
C Understand the fundamental limitations of computer algorithms by studying
O undecidable languages.
3
C Apply the abstract mathematical reasoning skills learned elsewhere.
O
4
A. Mapping of CO-PO-Taxonomy Domain & Level- Delivery-Assessment Tool:
Sl. CO Description PLOs Bloom’s Delivery Assessment
taxonomy methods tools
domain/level and
activities
C Demonstrate mastery over regular PLO1 Cognitive/Un Discussion, Quiz, Exam,
O languages, regular expressions, and derstanding Q/A. Assignment
1 deterministic finite automata.
C Demonstrate mastery over context-free PLO2 Cognitive/ Lectures, Quiz, Exam,
O languages, context-free grammars, and Analyzing Discussion, Assignment
2 pushdown automata. Q/A.
C Understand the fundamental limitations PLO2 Cognitive/ Lectures, Quiz, Exam,
O of computer algorithms by studying Analyzing Discussion, Assignment
3 undecidable languages. Q/A.
C Apply the abstract mathematical PLO4 Cognitive/ Lectures, Quiz, Exam
O reasoning skills learned elsewhere. Analyzing Discussion,
4 Q/A.
E. Course Materials:
i. Text and Reference Books:
Sl. Title Author(s) Yea Edition Publisher
r
01 Introduction to the Theory Michael Sipser 2013 3rd Cengage
of Computation
02 Introduction to Automata John E. Hopcroft, 2006 3rd Prentice
Theory, Languages, and Rajeev Motwani, Hall
Computation. Jeffrey D. Ullman.
F. Assessment Tools:
Assessment Tools Weightage (%)
Attendance 10%
Assignments 10%
Quizzes 20%
Midterm 25%
Final 35%
G. Lesson Plan:
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.
Week 2 Lecture 3: Problem-Solving on Designing DFAs.
Lecture 4: Closure of Regular Languages Under Union: The Cross-Product Construction.
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.
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.
Week 5 Lecture 8: More Examples of Regular Expressions, Converting Regular Expressions to NFAs.
Lecture 9: Converting DFAs to Regular Expressions using State Elimination.
Week 6 Quiz 2 (NFAs and Regular Expressions) and Discussion.
Lecture 10: Nonregular Languages, the Pumping Lemma for Regular Languages.
Week 7 Midterm Week
Week 8 Lecture 11: Introduction to Context-Free Grammars (CFG) and Context-Free Languages (CFL).
Lecture 12: CFGs continued, Parse Trees, Derivations, and Ambiguities.
Week 9 Lecture 13: Designing CFGs and Discussion.
Quiz 3 (Context-Free Grammars) and Discussion.
Week 10 Lecture 14: Putting a Grammar into Chomsky Normal Form.
Lecture 15: The Cocke-Younger-Kasami Algorithm.
Week 11 Lecture 16: Introduction to Pushdown Automata (PDA)
Lecture 17: Designing PDAs and Examples.
Week 12 Quiz 4 (CNF, CYK, and PDAs) and Discussion.
Lecture 18: Review
H. CO Assessment Plan:
Assessment Course Outcomes
Tools CO1 CO2 CO3 CO4
Quizzes √ √ √
Assignments √ √ √
Midterm √ √
Final √ √ √