COURSE DESCRIPTION

NAME OF INSTITUTION Lahore Garrison University
PROGRAM (S) TO BE EVALUATED Computer Science , Fall 2021
Course Description : We begin with a study of finite automata and the languages they can define (the so-called "regular languages." Topics include deterministic and nondeterministic automata, regular expressions, and the equivalence of these language-defining mechanisms. We also look at closure properties of the regular languages, e.g., the fact that the union of two regular languages is also a regular language. We consider decision properties of regular languages, e.g., the fact that there is an algorithm to tell whether or not the language defined by two finite automata are the same language. Finally, we see the pumping lemma for regular languages - a way of proving that certain languages are not regular languages. Our second topic is context-free grammars and their languages. We learn about parse trees and follow a pattern similar to that for finite automata: closure properties, decision properties, and a pumping lemma for context-free languages. We also introduce the pushdown automaton, whose nondeterministic version is equivalent in language-defining power to context-free grammars. Next, we introduce the Turing machine, a kind of automaton that can define all the languages that can reasonably be said to be definable by any sort of computing device (the so-called "recursively enumerable languages"). We shall learn how "problems" (mathematical questions) can be expressed as languages. That lets us define problems to be "decidable" if their language can be defined by a Turing machine and "undecidable" if not. We shall see some basic undecidable problems, for example, it is undecidable whether the intersection of two context-free languages is empty. Last, we look at the theory of intractable problems. These are problems that, while they are decidable, have almost certainly no algorithm that runs in time less than some exponential function of the size of their input. We meet the NP-complete problems, a large class of intractable problems. This class includes many of the hard combinatorial problems that have been assumed for decades or even centuries to require exponential time, and we learn that either none or all of these problems have polynomial-time algorithms. A common example of an NP-complete problem is SAT, the question of whether a Boolean expression has a truth-assignment to its variables that makes the expression itself true.
Course Code CSC353
Course Title Theory of Automata
Credit Hours 3+0
Prerequisites by Course(s) and Topics Discrete Structures
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 Saba Noor
URL (if any) https://www.tutorialspoint.com/automata_theory/index.htm
Current Catalog Description 1. Regular Languages 2. Finite Automata 3. Non-Determinism 4. Regular Expressions 5. Non-Regular Languages 6. Context-Free Languages 7. Pushdown Automata 8. Non-Context-Free Languages 9. Computability Theory 10. Church-Turing Thesis 11. Turing Machines
Textbook (or Laboratory Manual for Laboratory Courses) Introduction to computer theory, Daniel I. A. Cohen, 2nd Edition
Reference Material Introduction to computer theory, Daniel I. A. Cohen, 2nd Edition
Course Goals The objective of this course is to explore the theoretical foundations of computer science from the perspective of formal languages and classify machines by their power to recognize languages.
Course Learning Outcomes (CLOs):
At the end of the course the students will be able to:DomainBT Level*
understand the basic properties of formal languages and grammars. BT 1
Explain and manipulate the different concepts in automata theory and formal languages such as formal proofs, (non-)deterministic automata, regular expressions, regular languages, context-free grammars, context-free languages, Turing machines; BT 2
Determining the language accepted by an automata or generated by a regular expression or a context free grammar. BT 2
Design automata, regular expressions and context free grammars for accepting or generating a certain language. BT 4
Evaluating the algorithms and decision procedures for regular languages and context free grammar BT 5
Creating Turing machine for recursive language BT 6
* 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)
WeekLectureTopics Covered
Week 1 1 General Introduction to Automata Theory
2 Book Chapter 01 Introduction (What is automata theory)
Week 2 3 Chapter 02 Languages
4 Chapter 02 Languages and Practice Question
Week 3 5 Kleene Star, Kleene Plus Theorem and its proofs
6 Recursive Definition & Theorems
Week 4 7 Regular Languages
8 Regular expressions
Week 5 9 Chapter 05 Finite Automata
10 Finite Automata practice questions + Assignment
Week 6 11 Chapter 06 Transition Graphs
12 NFA to DFA and DFA to NFA
Week 7 13 Chapter 09 Moore and Melay Machines
14 chapter 09 Melay Machines Quiz#02
Week 8 1 hours Mid Term
Week 9 15 Moore to melay and melay to moore machine cinversins
16 Moore to melay and melay to moore machine conversions
Week 10 17 CFG and CFL
18 CFG, Right liner grammar, Left liner grammar and relationship
Week 11 19 Parse Tree, Types of Parse Tree, Examples, Ambiguity, Precidence
20 Left-Recursive
Week 12 21 Chapter 17: Push Down Automata Simple
22 Push Down Automata Complex
Week 13 23 Introduction to JFLAP Tool
24 JFLAP Tool Implementation
Week 14 25 PDA
26 Written Quiz 03
Week 15 27 Turing Machine
28 Turing Machine
Week 16 29 JFLAP Tool (Push Down automata and turning machine)
30 Project Presentation
Week 17 2 hours Final Term
Laboratory Projects/Experiments Done in the Course
Programming Assignments Done in the Course 3 assignments
Instructor Name Saba Noor
Instructor Signature
Date