| Course Code |
CSC353 |
| Course Title |
Theory of Automata |
| Credit Hours |
3+0 |
| Prerequisites by Course(s) and Topics |
Nill |
| Assessment Instruments with Weights (homework, quizzes, midterms, final, programming assignments, lab work, etc.) |
SESSIONAL (Quizzes, Assignments, Presentations) =25 %
Midterm Exam =25 %
Final Exam = 50%
|
| Course Coordinator |
Dr. Umer Farooq |
| URL (if any) |
|
| Current Catalog Description |
|
| Textbook (or Laboratory Manual for Laboratory Courses) |
Introduction to computer theory, Daniel I. A. Cohen, 2nd Edition |
| Reference Material |
An Introduction to Formal Languages and Automata, by Peter Linz, 4thedition, Jones & Bartlett Publishers, 2006, • Automata, Computability and Complexity: Theory and Applications, by Elaine Rich, 2011 |
| Course Goals |
On successful completion of this course, students will be able to answer these questions: • Explain and manipulate the different concepts in automata theory and formal languages such as formal proofs, automata, regular expressions, Turing machines etc. • Prove properties of languages, grammars and automata with rigorously formal mathematical methods • Differentiate and manipulate formal descriptions of languages, automata and grammars with focus on regular and context-free languages, finite automata and regular expressions. • Design automata, regular expressions and context-free grammars accepting or generating a certain language; |
| Course Learning Outcomes (CLOs): |
| At the end of the course the students will be able to: | Domain | BT Level* |
|---|
| will be able Understanding basic concept of Automata theory |
C |
3 |
| Will be able to apply formal languages and regular Expression for the problem solving |
C |
3 |
| * BT= Bloom’s Taxonomy, C=Cognitive domain, P=Psychomotor domain, A= Affective domain |
|
|
|
| Topics Covered in the Course, with Number of Lectures on Each Topic (assume 15-week instruction and one-hour lectures) |
| Week | Lecture | Topics Covered |
|---|
| Week 1 |
1 |
General Introduction |
|
2 |
Languages, Practice Questions |
| Week 2 |
3 |
Kleene Star, Recursive Definition |
|
4 |
Recursive Definition & Theorems |
| Week 3 |
5 |
Regular Languages |
|
6 |
Regular Languages |
| Week 4 |
7 |
Regular expressions |
|
8 |
Regular expressions |
| Week 5 |
9 |
Finite Automata FA practice examples |
|
10 |
Transition Graphs practice examples |
| Week 6 |
11 |
NFA to DFA |
|
12 |
NFA to DFA practice examples |
| Week 7 |
13 |
Push Down Automata |
|
14 |
Push Down Automata |
| Week 8 |
1 hours |
Mid Term |
| Week 9 |
15 |
Push Down Automata practice examples |
|
16 |
Push Down Automata practice examples |
| Week 10 |
17 |
Push Down Automata and CFL |
|
18 |
JFLAP |
| Week 11 |
19 |
CFG |
|
20 |
CFG, Right liner grammar, Left liner grammar and relationship |
| Week 12 |
21 |
Parse Tree, Types of Parse Tree, Examples, Ambiguity, Precedence |
|
22 |
Left-Recursive |
| Week 13 |
23 |
Types of Parsing, Top-Down Parsing Introduction, Bottom Up Parsing, Backtracking |
|
24 |
Predictive Parsers |
| Week 14 |
25 |
Turing Machine |
|
26 |
Turing Machine and JFLAP |
| Week 15 |
27 |
Presentations/Project |
|
28 |
Presentations/Project |
| Week 16 |
29 |
Revision |
|
30 |
Revision |
| Week 17 |
2 hours |
Final Term |
|
| Laboratory Projects/Experiments Done in the Course |
|
| Programming Assignments Done in the Course |
|
