National Computing Education Accreditation Council
NCEAC
NCEAC.FORM.001.D
COURSE OUTLINE PROGRAM (S) TO BE
EVALUATED
INSTITUTION University of Management &
Technology, Lahore BS Computer Science Course Description
NCEAC.FORM. 001-D
Course Code CS-3043
Course Title Theory of Automata
Credit Hours 3
Prerequisites by
Course(s) and Topics
Assessment Assignments 10%
Instruments with Quiz’s 5%
Weights Viva 15%
(homework,
quizzes, midterms, Project 20%
final, Class Activities 5%
programming Mid Term 20%
assignments/Proje Final Term 25%
ct, lab work, etc.)
Course Moderator Miss Nitasha Arooj Janjua
URL (if any)
Current Catalog
Description
Textbook (or Introduction to Computer Theory 2nd Edition by Danial I. A. Cohen
Laboratory
Manual for
Laboratory
Courses)
Reference Material Theory of Computation by Michael Sisper 2nd Edition
National Computing Education Accreditation Council
NCEAC
NCEAC.FORM.001.D
Course Goals The goal of the course is to familiarize the students with the concept of formal
languages, different classes of formal languages such as regular languages,
context free languages, context-sensitive languages, and recursive and
recursively enumerable languages. Students will also get knowledge about the
grammar and machines used for describing various types of languages. These
include regular expressions, finite state automata, context-free grammars, push-
down automata, and Turing machines. The properties of different types of
languages will also be discussed.
Course Learning Outcomes (CLOs):
CLOs Description Domain &
BT Level *
CLO 1 Describe the role of abstract computational models to Cognitive,
define which computational problems are solvable and Two(C2)
which are not.
CLO 2 Illustrate the concepts of Language, Grammar, and Cognitive,
Automata for Regular Languages, as well as their Two(C3)
applications in computing systems.
CLO 3 Illustrate the concepts of Language, Grammar, and Cognitive,
Automata for Context-Free Language, as well as their Three(C3)
applications in computing systems.
CLO 4 Understand the Turing machines and their applications in Cognitive,
computing systems. Two(C2)
* BT= Bloom’s Taxonomy, C=Cognitive domain, P=Psychomotor domain, A= Affective domain
National Computing Education Accreditation Council
NCEAC
NCEAC.FORM.001.D
Mapping of CLOs to Program Learning Outcomes (PLOs):
CLOs/PLOs CLO 1 CLO 2 CLO 3 CLO 4
PLO 1: Academic Education ✓
PLO 2: Knowledge for Solving ✓ ✓ ✓
Computing Problems
PLO 3: Problem Analysis
PLO 4: Design and Development of Solutions
PLO 5: Modern Tool Usage
PLO 6: Individual and Teamwork
PLO 7: Communication
PLO 8: Computing Professionalism and Society
PLO 9: Ethics
PLO 10: Life-Long Learning
National Computing Education Accreditation Council
NCEAC
NCEAC.FORM.001.D
Lecture Plan
Topics
Co
ve
re
d
Week Topics Assessments CLOs
1 Introduction to Automata
Theory
Finite Automata
2 Deterministic Finite Quiz 1 CLO1
Automata (DFA).
in
the
Co
ur
se,
wit
h
Nu
m
be
r
of
Le
ctu
res
on
Ea
ch
To
pic
3 Non-Deterministic Assignment -1 CLO1
Finite Automata (NDFA)
National Computing Education Accreditation Council
NCEAC
NCEAC.FORM.001.D
4 Minimization of DFA
Regular Expressions
5 Operations on Regular Assignment -2 CLO2
expressions
Finite Automata and
Regular Expressions.
6 TG and GTG Quiz-2 CLO2
Equivalence of
Deterministic and Non-
Deterministic Finite
Automata
7 Kleene’s Theorem
8 Pumping Lemma for
Regular Languages.
Closure Properties of
Regular Languages
9 Revision and MidTerm Mid Term CLO1,
CLO2,
10 Mealy Moore Machines. Assignment -3 CLO3
Conversion from Mealy
to Moore and vice
versa.
11 Context-Free
Grammars; Regular
Grammars; Parse Trees
12 Ambiguity in Grammars Quiz-3 CLO3
and Languages.
Standard Forms;
Chomsky Normal
Forms;
13 Deterministic and Non Assignment -4 CLO4
Deterministic (PDA);
Formal definition of NPDA.
Transition functions of
NPDA; NPDA
Execution; Accepting
Strings with NPDA;
Equivalence of PDAs
and CFG.
National Computing Education Accreditation Council
NCEAC
NCEAC.FORM.001.D
14 Turing machines and
decidability
15 Complexity Quiz-4 CLO4
issues and analysis
P and NP problems
Laboratory
Projects/ Experiments Done in the Course
1 programming assignments/project+viva
3 hours per week
CLOs Midterm
Exam
1 ✔ ✔ ✔
2 ✔ ✔ ✔
3 ✔ ✔
4 ✔ ✔
Instructor Name: Muhammad Adeel Ashraf
Instructor Signature ________________________
5
NCEAC.FORM.001.D
