Faculty of C & IT
Department of Computer Science
Title Theory of Automata and Formal Languages
Code CS-361
Credit Hours Theory/week:
Weight 3 Cr. Hrs.
Contact Hours 3 Hrs
Lectures 2
Duration 1.5 Hrs
Instructor Najeeb Ur Rehman, Assistant Professor, CS-Dept.
Email
[email protected]Prerequisite Discrete Structures
Category Core
Aims and Objectives • The goal of this course is to make the students familiar with fundamental principles of
computability.
• To give them an insight into the theory and design of problem solving in conventional and
modem computing machines.
• To bring a practical approach in the students, so that they can initiate design and implement
solution of a problem.
• To give them the understanding of mathematical models of the computing machines.
• To provide them the mathematical maturity of computer science.
• To analyze the properties and limitations of mathematical models of the computing
machines.
• To understand the decidability and computability of the computational problems.
• To make students able to practically implement the ideas gained in the subject of Modem
programming languages.
• To prepare students for the study of compiler construction.
Learning Outcomes • The students will have a better understanding of defining formal languages so that they may
define different constructs of any programming language.
• To acquaint the students with the recursive iteration of parts of procedure using Context Free
Grammars.
• Will be able to have the understanding of formal languages in the context of computational
machines.
• Will be able to have mathematical understanding to computational machines.
• Will give the students an insight of the evolution of Computers by showing them the
working of Turing machines.
• Will be able to understand the limitations of the computational machines
• Will be able to understand the solvability of the problems.
• Will be able to analyze the problems and design the solutions.
• To familiarize the students with Push Down Automata so that they may design parser in
Compiler Construction.
Syllabus Finite State Models: Language definitions preliminaries, Regular expressions/Regular languages,
Finite automata (FAs), Transition graphs (TGs), NFAs, Kleene’s theorem, Transducers (automata with
output), Pumping lemma and non regular language Grammars and PDA: Context free grammars,
Derivations, derivation trees and ambiguity, Simplifying CFLs , Normal form grammars and parsing,
Decidability, Turing Machines Theory: Turing machines, Defining Computers by TMs.
Text Book/s A. “Introduction to Computer Theory”, Daniel I. A. Cohen, ISBN: 0072496681
Reference Material A. “An Introduction to Formal Languages and Automata”, Peter Linz
B. “ Automata, Computability and Complexity: Theory and Applications”,
by Elaine Rich, 2011
Resources • Photocopy/Printer Facility for Handouts
Sessional Mid Term Final Term
Assessment Criteria 25% 25% 50%
Note: All the quizzes will be announced or unannounced.
Framework
Required
Source (Book-
Week Lecture Topic Study
Chapter No.)
Hours
Introduction to Automata theory, Its A. Ch#1, Ch#2
background, Formal Languages,
Introduction to defining languages,
1
alphabet, language, word, null string,
length of a string, reverse of a string,
1
Palindrome, Kleene closure.
Formal definition of Regular A. Ch#4
Expressions, Defining languages with
2
regular expressions, Languages
associated with regular expressions.
Equality of Regular Expressions, A. Ch#4 Assignment #1
Introducing the language EVEN-
3
EVEN. More examples related to
regular expressions.
2
Introducing Finite Automata., A. Ch#4 Quiz# 01
Defining languages using Finite
4
Automata. Constructing Finite
Automata for different languages.
Recognizing the language defined by A. Ch#5 Assignment #2
5 the given Finite Automata. More
examples related to Finite Automata.
3 Transition Graphs with examples, A. Ch#5
Generalized Transition Graphs, Non-
6
determinism in case of Transition
Graphs.
Non-deterministic FA’s. Differences A. Ch#6 Quiz #02
between DFA and NFA. More
7
examples related to NFA.Transition
4 Functions, Tansition Table
Kleene’s Theorem: Converting A. Ch#7
Regular Expression into FA’s.
8
Converting NFA into Regular
Expression
Kleene’s Theorem: converting NFA A. Ch#7 Assignment #3
9
into DFA
5
Finite Automata with output. Moore A. Ch#8
10
and Mealy Machines
Regular Languages, Closure properties A. Ch#9
(i.e. Union, Concatenation, Kleene
closure, Complements and
11
Intersections) of Regular Languages
with examples. Properties by applying
6
kleene’s theorem
Decidability, decision procedure, A. Ch#7 Quiz# 03
Effective decision procedure to prove
12 whether two given RE’s or FA’s are
equivalent. Checking whether
languages are finite or infinite.
Non-Regular Languages, The pumping A. Ch#9
7 13
Lemma,
More Examples relating to Pumping A. Ch#9
14
Lemma.
A. Ch#11
15
Critical Discussion and Revision
8 Mid Term
16
Context-Free Grammars, Formal A. Ch#12
17 Definition of CFG. CFG’s for Context
Free Languages.
9 CFG’s of PALINDROME, More A. Ch#12 Assignment #4
Examples of CFL’s. Leftmost and
18
Rightmost derivations. Parse Trees,
Examples relating to Parse Trees,
Ambiguous and Unambiguous CFG’s, A. Ch#12 Quiz#4
19 CFG conversion into NFA,
10
Total language tree. Lukasiewicz A. Ch#12
20
notation, Backus Naur Form (BNF)
Simplification of CFG’s. Killing null A. Ch#13
21 productions, Killing unit productions,
11 Killing of useless Production
CNF introduction, Chomsky Normal A. Ch#13
22
Form (CNF) with examples,GNF
Pushdown Automata, Pushdown stack. A. Ch#14
23
Nondeterministic PDA.
12
Examples related with PDA, PDA for A. Ch#14
24
Odd Palindrome, Even Palindrome
Proving CFG = PDA with examples( A. Ch#15
25
CFG conversion into PDA)
13 Context Free Languages, their Closure A. Ch#17 Presentations
26 Properties, Union, Concatenation and
Kleene Closures using CFG’s.
27 Context free languages Examples A. Ch#17
Turing Machines (TM), Formal A. Ch#18
14
28 Definition of TM, Turing Decidable
Languages.
29 TM with Non-Context Free Languages A. Ch#19
15
30 Turing Recognizable Languages A. Ch#19
Defining Computers by TM’s.
31 A. Ch#25
16
Computable Functions
32
Final Revision
