Lecture 1
Lecture 1
Lecture 1
▪ The major objective of this course is to introduce the student to the concepts of theory
of automata in computer science. The student should acquire insights into the
relationship among formal languages, formal grammars, and automata.
▪ Upon successful completion of this course, students will be able to:
▪ Understand the equivalence between Nondeterministic Finite State Automata and
Deterministic Finite State Automata.
▪ Understand the equivalence between Context-Free Grammars and
Nondeterministic Pushdown Automata.
▪ Appreciatethe power of the Turing Machine, as an abstract
automaton,that describes computation, effectively and efficiently.
► Text Book
► Introduction to computer theory, Daniel I. A. Cohen, 2nd Edition
► Reference Books
► Automata, Computability and Complexity: Theory and Applications, by Elaine Rich, 2011
► An Introduction to Formal Languages and Automata, By Peter Linz, 4 edition, Jones & Bartlett Publishers, 2006
th
► Theory of Automata, Formal Languages and Computation, By S. P. Eugene, Kavier, 2005, New Age Publishers, ISBN
(10): 81-224-2334-5, ISBN (13): 978-81-224-2334-1.
► Introduction to Automata Theory, Languages, and Computation, John Hopcroft and Jeffrey Ullman, 2nd edition, 2001,
Addison-Wesley.
► Introduction to Languages and the Theory of Computation, By John C. Martin 3rd edition, 2002, McGraw-Hill
Professional.
► Discrete Structures
► Following contents will be covered throughout the semester in week wise lectures:
► Background and Languages
► Recursive Definitions and Regular Expressions
► Finite Automata
► Transition Graphs
► Kleene’s Theorem
► Nondeterminism
► Finite Automata with Output
► Regular Languages and Non-regular Languages
► Context-Free Grammars and Regular Grammars
► Trees
► Chomsky Normal Form
► Pushdown automata
► Sessional
► Home Assignments
► Quizzes
► Project
► Presentations
► Mid Exam
► Final Exam
Different names;
• Theory of Automata
• Automata Theory
• Theory of Computer Science
• Theory of Computation
• Computer Theory
14
Automata Theory
► A set is a group of objects, called elements (or members) of this set. For example, the
students in this room form a set.
► A set can be defined by listing all its elements inside braces, e.g.:
► S ={ 7,21,57}
► The order of elements in sets do not matter – in particular, S={7,21,57} = {21,57,7}
► The set with no elements is called the empty set and denoted by Λ
► The empty set is a subset of every set.
► The set of natural numbers N (or N):
► N = {1, 2, 3, . . .}
► The set of integers Z (or Z):
► Z = {. . ., -2,-1, 0, 1, 2,…}
► It is clear that N is the subset of Z