| Course Code |
CSC353 |
| Course Title |
Theory of Automata |
| Credit Hours |
3+0 |
| Prerequisites by Course(s) and Topics |
NA |
| 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 |
1) Automata, Computability and Complexity: Theory and Applications, by Elaine Rich, 2011 2) An Introduction to Formal Languages and Automata, by Peter Linz, 4thedition, Jones & Bartlett Publishers, 2006 3)Theory of Automata, Formal Languages and Computation, by S. P. Eugene, Kavier, 2005, New Age Publishers |
| Course Goals |
1)Explain and manipulate the different concepts in automata theory and formal languages such as formal proofs, automata, regular expressions, Turing machines etc. 2) Prove properties of languages, grammars and automata with rigorously formal mathematical methods 3) Differentiate and manipulate formal descriptions of languages, automata and grammars with focus on regular and context-free languages, finite automata and regular expressions. 4) 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* |
|---|
| Explain and manipulate the different concepts in automata theory and formal languages such as formal proofs, automata, regular expressions, Turing machines etc. |
C |
3 |
| Prove properties of languages, grammars and automata with rigorously formal mathematical methods |
C |
3 |
| Differentiate and manipulate formal descriptions of languages, automata and grammars with focus on regular and context-free languages, finite automata and regular expressions. |
C |
4 |
| Design automata, regular expressions and context-free grammars accepting or generating a certain language; |
P |
4 |
| * 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 |
Introduction to Theory of automata and Course Description |
|
2 |
Under standing of Languages, |
| Week 2 |
3 |
Kleene Star, Descriptive and Recursive of Languages |
|
4 |
Recursive Definition & Theorems |
| Week 3 |
5 |
Regular Languages and Regular Expression |
|
6 |
Regular Languages |
| Week 4 |
7 |
Regular expressions |
|
8 |
Regular expressions |
| Week 5 |
9 |
Finite Automata |
|
10 |
Transition Graphs practice examples |
| Week 6 |
11 |
Types of Finite automata (DFA, NFA) |
|
12 |
NFA to DFA practice examples |
| Week 7 |
13 |
Conversion NFA to DFA |
|
14 |
Moore and Mealy Machines |
| Week 8 |
1 hours |
Mid Term |
| Week 9 |
15 |
Push Down automata |
|
16 |
Push Down Automata practice examples |
| Week 10 |
17 |
Push Down Automata |
|
18 |
Push Down automata examples |
| Week 11 |
19 |
Context Free Grammar |
|
20 |
String Parsing, Top down Bottom Up Parsing |
| Week 12 |
21 |
Left Parsing , Right Parsing, |
|
22 |
Parse Tree, Types of Parse Tree, Examples, Ambiguity, Precedence |
| Week 13 |
23 |
Total Tree Derivation |
|
24 |
Turing Machine |
| 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 |
|
