Lecture 1

Download as pdf or txt
Download as pdf or txt
You are on page 1of 20

1

Lahore Garrison University


CSC353- Theory of Automata
Week-1
Semester-#4 Fall 2022
2
Instructor Contact Details

► Instructor Name: Tayyaba Sultana


► Course : Theory of Automata
► Credit Hours: 3
► Office Location: CS Staff Room 3rd floor NB
► Email: tayyabasultana@lgu.edu.pk
► Visiting Hours: Tuesday 11:00 am to 12:00 pm

Lahore Garrison University


3
Course Objectives

▪ 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.

Lahore Garrison University


4
Learning Outcomes

► At the end of the course the students will be able to:


► Explain and manipulate the different concepts in automata theory and formal languages such as
formal proofs, automata, regular expressions, Turing machines etc.
► Prove properties of languages, grammars and automata with rigorously formal mathematical
methods
► Design of automata, RE and CFG
► Transform between equivalent NFAs, DFAs and Res
► Define Turing machines performing simple tasks.
► Differentiate and manipulate formal descriptions of languages, automata and grammars with
focus on regular and context-free languages, finite automata and regular expressions.

Lahore Garrison University


5
Books

► 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.

Lahore Garrison University


6
Course Prerequisites

► Discrete Structures

Lahore Garrison University


7
Course Contents according to
HEC
► 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, Context sensitive languages, grammars and
linear bounded automata (LBA), Chomsky’s hierarchy of grammars Turing
Machines Theory: Turing machines, Post machine, Variations on TM, TM
encoding, Universal Turing Machine, Defining Computers by TMs.

Lahore Garrison University


8
Course Contents

► 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

Lahore Garrison University


9
Teaching
Methodology:
► Lectures
► Written Assignments
► Semester Project
► Presentations

Lahore Garrison University


10
Course Assessment:

► Sessional
► Home Assignments
► Quizzes
► Project
► Presentations

► Mid Exam
► Final Exam

Lahore Garrison University


11
Evaluation and Awarding Marks
Criteria

Lahore Garrison University


12
Theory of Automata

Lahore Garrison University


13
What does “automata” mean?

► It is the plural of automaton, and it means “something that works automatically”

Lahore Garrison University


Def.
Is an area of computer science that deals with the study of
abstract machines (mathematical models) as well as the
computational problems that can be solved using them

Different names;

• Theory of Automata
• Automata Theory
• Theory of Computer Science
• Theory of Computation
• Computer Theory
14
Automata Theory

► Deals with the definitions and properties of mathematical model of computation.


► Examples: Finite automata, Context free grammars.
► Finite Automaton: Text Processing, Compilers
► Context Free grammars: Programming languages, AI

Lahore Garrison University


15
SETS

► 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}

Lahore Garrison University


16
Cont..

► The membership is denoted by ϵ symbol. For example, 21 ϵ S but 10 not belong to S.


► If every member of A is also a member of B. We say that A is a subset of B and if A is a
subset of B but not equal to B then A is proper subset of B and written as A ⊂B. If A is a
subset of B and A is equal to B then A is improper subset of B and write as A⊆B.

Lahore Garrison University


17
Examples

► 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

Lahore Garrison University


18
Set Operations

Lahore Garrison University

You might also like