Theory Of Automata

1
Course Details
 Course Title : Theory of Automata
 Credit hours : 2+0
 Recommended Books:

1. Introduction to Computer Theory, by

Daniel I. Cohen, John Wiley and Sons, Inc.,
1991, Second Edition (as a Text Book)
2. Introduction to Languages and Theory of
Computation, by J. C. Martin, McGraw Hill
Book Co., 1997, Second Edition (for
Additional Reading)

2
Marks Distribution
 Assignments
 Quizzes
 Mid-term
 Theory paper
 Presentation

3
DON’T FORGET
 75%of the attendance is compulsory to be
appear in the Final exam

4
 Let’s get started……

5
Lecture # 01
Theory of Automata

6
What is an Automaton?
 Generally speaking, an automaton (plural
automata) is a self operating machine.
 An abstract machine , a mathematical model.

Automaton = An abstract computing device

7
What is Automata?
 It is the plural of automaton, and it means
“something that works automatically”.

8
What does Theory of Automata
mean?

 The word “Theory” means that this

subject is a more mathematical subject
and less practical.
 However, this subject is the foundation

for many other practical subjects.

 In general, this subject focuses on the

theoretical aspects of computer science.

9
Some other names ,
 Theory of Computer Science
 Theory of Computation
 Computer Theory
 Automata Theory

10
Theory of Automata
 Automata theory is the study of abstract
computational devices and the computational
problems that can be solved using them.

 Abstract devices are (simplified) models of

real computations

11
Applications
 Helps in design and construction of
different software's and what we can expect
from our software's.
 Automata plays a major role in:

◦ Theory of Computation
◦ Compiler Construction
◦ Parsing
◦ Formal Verification
◦ Defining computer languages
◦ Artificial Intelligence

12
Introduction to Languages
 Machines work on certain instructions
(language).
 Instructions must be given in a proper way

so that machine can understand it.

 It deals with the study of abstract machine as

well as computational problems

13
Types of Languages
Informal language (Talking languages)
Programming language
Formal Languages (Syntactic languages)

Will discuss it later but first we must know

what is a language ….

14
Language
 A set of strings with some rules.
 Made up of letters , characters and symbols.
 Letters : Characters and symbols which

combine to form a language for a machine.

 Example: [a,b,c,….] ,[0,1,2,….]

15
Alphabets:
 A finite non-empty set of symbols (letters)
 It is denoted by Σ ( Greek letter sigma).

Example
Σ = {a, b} (Two character language)
Σ = {0,1} (Binary language)

16
Defining Alphabets – Guidelines
The following are three important rules for
defining Alphabets for a language:
 Should not contain empty symbol Λ
 Should be finite. Thus, the number of
symbols are finite
 Should not be ambiguous

17
Ambiguity
Example:
 An alphabet may contain letters consisting of
group of symbols for example
Σ1= {A, aA, bab, d}.

Now consider an alphabet

Σ2= {A, Aa, bab, d} and a string AababA.

18
 This string can be factored in two
different ways
◦ (Aa), (bab), (A)
◦ (A), (abab), (A)
Which shows that the second group
cannot be identified as a string, defined
over Σ = {a, b}.
 This is due to ambiguity in the defined

alphabet Σ2

19
 Why Ambiguity comes: A computer program
first scans A as a letter belonging to Σ2, while
for the second letter, the computer program
would not be able to identify the symbols
correctly.
 Ambiguity Rule:- The Alphabets should be

defined in a way that letters consisting of

more than one symbols should not start with
a letter, already being used by some other
letter.

20
Ambiguity Examples
 Σ1= {A, aA, bab, d}
 Σ2= {A, Aa, bab, d}
Σ1 is a valid alphabet while Σ2 is an in-valid
alphabet.
Similarly,
 Σ = {a, ab, ac}
1
 Σ2= {a, ba, ca}
In this case, Σ1 is a invalid alphabet while Σ2 is
a valid alphabet.

21
String
 Concatenation of finite symbols from the

alphabet.
 Formed by combining various symbols from

an alphabet.

Example:
If Σ= {a, b} then
a, aa, ab, bb, abab, aabb,
ababababababababab

22
Example
Make a language for a machine from alphabet
{a,b} in which strings starts and ends with ‘a’

23
Word
 Strings belonging to some language
 A string that is permissible in language

Example:
If Σ= {a} then a language L can be defined as
L={a,aa,aaa,….}

NOTE:
All words are strings, but not all strings are words

24
Empty String
 A string with no symbol at all
 Denoted by (Small Greek letter Lambda) λ or

(Capital Greek letter Lambda) Λ,

 Also called a null string

25
Length of string
 It is the number of letters in the string
 The length of string s, denoted by |s|

Example:
Σ={a,b}
s=ababa
|s|=5

The length of empty string will be equal to zero

26
Example:
Σ= {B, aB, bab, d}
s=BaBbabBd
Tokenization=(B), (aB), (bab), (B), (d) |s|=5

27
Reverse of string
 It is obtained by writing the letters of s in

reverse order.
 The reverse of a string s denoted by Rev(s) or

sr
Example:
If s = abc is a string defined over
Σ={a,b,c} then
Rev(s) or sr = cba

28
Example:
Σ= {B, aB, bab, d}
s=BaBbabBd
Tokenizing=(B) (aB) (bab) (B) (d)

Rev(s)=dBbabaBB

29
Example:
Σ= {A, aA, bab, d}
s=AaAbabAd
Rev(s)=dAbabaAA or
Rev(s)= dAbabAaA

Which one is correct?

30
Power of an alphabet
Determines that the string made from alphabet
will be of length equal to power of alphabet.

Formula: Number of strings of length ‘m’

defined over alphabet of ‘n’ letters is nm
where ,
n= Total number of letters in alphabet
m= Power/length

31
Examples:
The language of strings of length 2,
defined over Σ={a,b}
L={aa, ab, ba, bb} i.e. number of
strings = 22

The language of strings of length 3,

defined over Σ={a,b}
L={aaa, aab, aba, baa, abb, bab, bba,
bbb} i.e. number of strings = 23

32
Power of string
 Determine the length of the string

Example:
 (bab)2 = baba

 ba2 b= baab

33
Lecture Summary
 Definition of the word Automata
 Types of languages, empty/Null String,

Alphabets , Ambiguity, words, length of

strings.
 Power of alphabets and strings

34