Table of contents:
Lecture N0. 1 .................................................................................................................... 3
What does automata mean? .......................................................................................... 3
Introduction to languages.............................................................................................. 3
Alphabets...................................................................................................................... 3
Strings .......................................................................................................................... 3
Defining Languages ....................................................................................................... 4
Lecture N0. 2 .................................................................................................................... 7
Kleene Star Closure....................................................................................................... 7
Recursive definition of languages ................................................................................... 7
Lecture N0. 3 .................................................................................................................... 9
Regular Expression ....................................................................................................... 9
Recursive definition of Regular Expression(RE) .............................................................. 9
Method 3 (Regular Expressions)..................................................................................... 9
Lecture N0. 4 .................................................................................................................. 10
Equivalent Regular Expressions .................................................................................. 10
Method 4 (Finite Automaton) ....................................................................................... 11
Lecture N0. 5 .................................................................................................................. 13
Lecture N0. 6 .................................................................................................................. 15
Equivalent FAs............................................................................................................ 15
Lecture N0. 7 .................................................................................................................. 17
FA corresponding to finite languages ........................................................................... 17
Method 5 (Transition Graph)........................................................................................ 18
Lecture N0. 8 .................................................................................................................. 19
Examples of TGs: accepting all strings, accepting none, starting with b, not ending in b,
containing aa, containing aa or bb............................................................................... 19
Lecture N0. 9 .................................................................................................................. 21
Generalized Transition Graphs .................................................................................... 23
Lecture N0. 10 ................................................................................................................ 24
Nondeterminism.......................................................................................................... 25
Kleene’s Theorem ........................................................................................................ 25
Lecture N0. 11 ................................................................................................................ 26
Proof(Kleene’s Theorem Part II) .................................................................................... 26
Lecture N0. 12 ................................................................................................................ 30
Kleene’s Theorem Part III............................................................................................. 31
Lecture N0. 13 ................................................................................................................ 34
Lecture N0. 14 ................................................................................................................ 37
Lecture N0. 15 ................................................................................................................ 40
Nondeterministic Finite Automaton (NFA) ................................................................... 40
Converting an FA to an equivalent NFA........................................................................ 41
Lecture N0. 16 ................................................................................................................ 42
NFA with Null String ................................................................................................... 42
Lecture N0. 17 ................................................................................................................ 45
NFA and Kleene’s Theorem .......................................................................................... 45
Lecture N0. 18 ................................................................................................................ 48
NFA corresponding to Concatenation of FAs................................................................. 48
NFA corresponding to the Closure of an FA .................................................................. 50
Lecture N0. 19 ................................................................................................................ 52
Memory required to recognize a language..................................................................... 52
Distinguishable strings and Indistinguishable strings .................................................. 53
Lecture N0. 20 ................................................................................................................ 55
Finite Automaton with output...................................................................................... 55
Moore machine ........................................................................................................... 55
Lecture N0. 21 ................................................................................................................ 57
Mealy machine ............................................................................................................ 57
Lecture N0. 22 ................................................................................................................ 60
Equivalent machines ................................................................................................... 60
Lecture N0. 23 ................................................................................................................ 63
Lecture N0. 24 ................................................................................................................ 65
,Theory of Automata (CS402)
Regular languages....................................................................................................... 65
Complement of a language .......................................................................................... 66
Lecture N0. 25 ................................................................................................................ 68
Nonregular languages.................................................................................................. 71
Lecture N0. 26 ................................................................................................................ 72
Pumping Lemma ......................................................................................................... 72
Lecture N0. 27 ................................................................................................................ 75
Pumping Lemma version II .......................................................................................... 75
Lecture N0. 28 ................................................................................................................ 77
Pseudo theorem .......................................................................................................... 78
Lecture N0. 29 ................................................................................................................ 79
Decidability................................................................................................................. 79
Determining whether the two languages are equivalent or not ? ................................... 80
Lecture N0. 30 ................................................................................................................ 83
Lecture N0. 31 ................................................................................................................ 87
Context Free Grammar (CFG) ...................................................................................... 87
CFG terminologies....................................................................................................... 87
Lecture N0. 32 ................................................................................................................ 90
Trees........................................................................................................................... 91
Lecture N0. 33 ................................................................................................................ 93
Polish Notation (o-o-o) ................................................................................................. 94
Lecture N0. 34 ................................................................................................................ 96
Total language tree...................................................................................................... 96
Regular Grammar ....................................................................................................... 97
Lecture N0. 35 ................................................................................................................ 99
Null Production ........................................................................................................... 99
Lecture N0. 36 .............................................................................................................. 102
Chomsky Normal Form (CNF) .................................................................................... 102
Lecture N0. 37 .............................................................................................................. 105
A new format for FAs ................................................................................................. 105
Lecture N0. 38 .............................................................................................................. 109
Nondeterministic PDA ............................................................................................... 111
Lecture N0. 39 .............................................................................................................. 114
PDA corresponding to CFG ........................................................................................ 114
Lecture N0. 40 .............................................................................................................. 118
Conversion form of PDA............................................................................................. 119
Lecture N0. 41 .............................................................................................................. 121
Lecture N0. 42 .............................................................................................................. 124
Lecture N0. 43 .............................................................................................................. 127
Non-Context-Free language ....................................................................................... 127
Pumping lemma for CFLs .......................................................................................... 128
Lecture N0. 44 .............................................................................................................. 133
Decidablity................................................................................................................ 133
Parsing Techniques ................................................................................................... 136
Lecture N0. 45 .............................................................................................................. 140
Turing machine......................................................................................................... 140
Last Updated: December 20, 2011
[Please see Errata if you have copy of handouts printed before this date]
2
© Copyright Virtual University of Pakistan
,Theory of Automata (CS402)
Theory of Automata
Lecture N0. 1
Reading Material
Introduction to Computer Theory Chapter 2
Summary
Introduction to the course title, Formal and In-formal languages, Alphabets, Strings, Null string, Words, Valid
and In-valid alphabets, length of a string, Reverse of a string, Defining languages, Descriptive definition of
languages, EQUAL, EVEN-EVEN, INTEGER, EVEN, { an bn}, { an bn an }, factorial, FACTORIAL,
DOUBLEFACTORIAL, SQUARE, DOUBLESQUARE, PRIME, PALINDROME.
What does automata mean?
It is the plural of automaton, and it means “something that works automatically”
Introduction to languages
There are two types of languages
• Formal Languages (Syntactic languages)
• Informal Languages (Semantic languages)
Alphabets
Definition
A finite non-empty set of symbols (called letters), is called an alphabet. It is denoted by Σ ( Greek letter sigma).
Example
Σ = {a,b}
Σ = {0,1} (important as this is the language which the computer understands.)
Σ = {i,j,k}
Note Certain version of language ALGOL has 113 letters.
Σ (alphabet) includes letters, digits and a variety of operators including sequential operators such as GOTO and
IF
Strings
Definition
Concatenation of finite number of letters from the alphabet is called a string.
Example
If Σ = {a,b} then
a, abab, aaabb, ababababababababab
Note
Empty string or null string
Sometimes a string with no symbol at all is used, denoted by (Small Greek letter Lambda) λ or (Capital Greek
letter Lambda) Λ, is called an empty string or null string.
The capital lambda will mostly be used to denote the empty string, in further discussion.
Words
Definition
Words are strings belonging to some language.
Example
If Σ= {x} then a language L can be defined as
L={xn : n=1,2,3,…..} or L={x,xx,xxx,….}
Here x,xx,… are the words of L
Note
3
© Copyright Virtual University of Pakistan
, Theory of Automata (CS402)
All words are strings, but not all strings are words.
Valid/In-valid alphabets
While defining an alphabet, an alphabet may contain letters consisting of group of symbols for example Σ1= {B,
aB, bab, d}.
Now consider an alphabet
Σ2= {B, Ba, bab, d} and a string BababB.
This string can be tokenized in two different ways
(Ba), (bab), (B)
(B), (abab), (B)
Which shows that the second group cannot be identified as a string, defined over
Σ = {a, b}.
As when this string is scanned by the compiler (Lexical Analyzer), first symbol B is identified as a letter
belonging to Σ, while for the second letter the lexical analyzer would not be able to identify, so while defining
an alphabet it should be kept in mind that ambiguity should not be created.
Remarks
While defining an alphabet of letters consisting of more than one symbols, no letter should be started with the
letter of the same alphabet i.e. one letter should not be the prefix of another. However, a letter may be ended in a
letter of same alphabet.
Conclusion
Σ1= {B, aB, bab, d}
Σ2= {B, Ba, bab, d}
Σ1 is a valid alphabet while Σ2 is an in-valid alphabet.
Length of Strings
Definition
The length of string s, denoted by |s|, is the number of letters in the string.
Example
Σ={a,b}
s=ababa
|s|=5
Example
Σ= {B, aB, bab, d}
s=BaBbabBd
Tokenizing=(B), (aB), (bab), (B), (d)
|s|=5
Reverse of a String
Definition
The reverse of a string s denoted by Rev(s) or sr, is obtained by writing the letters of s in reverse order.
Example
If s=abc is a string defined over Σ={a,b,c}
then Rev(s) or sr = cba
Example
Σ= {B, aB, bab, d}
s=BaBbabBd
Rev(s)=dBbabaBB
Defining Languages
The languages can be defined in different ways , such as Descriptive definition, Recursive definition, using
Regular Expressions(RE) and using Finite Automaton(FA) etc.
Descriptive definition of language
The language is defined, describing the conditions imposed on its words.
4
© Copyright Virtual University of Pakistan
Lecture N0. 1 .................................................................................................................... 3
What does automata mean? .......................................................................................... 3
Introduction to languages.............................................................................................. 3
Alphabets...................................................................................................................... 3
Strings .......................................................................................................................... 3
Defining Languages ....................................................................................................... 4
Lecture N0. 2 .................................................................................................................... 7
Kleene Star Closure....................................................................................................... 7
Recursive definition of languages ................................................................................... 7
Lecture N0. 3 .................................................................................................................... 9
Regular Expression ....................................................................................................... 9
Recursive definition of Regular Expression(RE) .............................................................. 9
Method 3 (Regular Expressions)..................................................................................... 9
Lecture N0. 4 .................................................................................................................. 10
Equivalent Regular Expressions .................................................................................. 10
Method 4 (Finite Automaton) ....................................................................................... 11
Lecture N0. 5 .................................................................................................................. 13
Lecture N0. 6 .................................................................................................................. 15
Equivalent FAs............................................................................................................ 15
Lecture N0. 7 .................................................................................................................. 17
FA corresponding to finite languages ........................................................................... 17
Method 5 (Transition Graph)........................................................................................ 18
Lecture N0. 8 .................................................................................................................. 19
Examples of TGs: accepting all strings, accepting none, starting with b, not ending in b,
containing aa, containing aa or bb............................................................................... 19
Lecture N0. 9 .................................................................................................................. 21
Generalized Transition Graphs .................................................................................... 23
Lecture N0. 10 ................................................................................................................ 24
Nondeterminism.......................................................................................................... 25
Kleene’s Theorem ........................................................................................................ 25
Lecture N0. 11 ................................................................................................................ 26
Proof(Kleene’s Theorem Part II) .................................................................................... 26
Lecture N0. 12 ................................................................................................................ 30
Kleene’s Theorem Part III............................................................................................. 31
Lecture N0. 13 ................................................................................................................ 34
Lecture N0. 14 ................................................................................................................ 37
Lecture N0. 15 ................................................................................................................ 40
Nondeterministic Finite Automaton (NFA) ................................................................... 40
Converting an FA to an equivalent NFA........................................................................ 41
Lecture N0. 16 ................................................................................................................ 42
NFA with Null String ................................................................................................... 42
Lecture N0. 17 ................................................................................................................ 45
NFA and Kleene’s Theorem .......................................................................................... 45
Lecture N0. 18 ................................................................................................................ 48
NFA corresponding to Concatenation of FAs................................................................. 48
NFA corresponding to the Closure of an FA .................................................................. 50
Lecture N0. 19 ................................................................................................................ 52
Memory required to recognize a language..................................................................... 52
Distinguishable strings and Indistinguishable strings .................................................. 53
Lecture N0. 20 ................................................................................................................ 55
Finite Automaton with output...................................................................................... 55
Moore machine ........................................................................................................... 55
Lecture N0. 21 ................................................................................................................ 57
Mealy machine ............................................................................................................ 57
Lecture N0. 22 ................................................................................................................ 60
Equivalent machines ................................................................................................... 60
Lecture N0. 23 ................................................................................................................ 63
Lecture N0. 24 ................................................................................................................ 65
,Theory of Automata (CS402)
Regular languages....................................................................................................... 65
Complement of a language .......................................................................................... 66
Lecture N0. 25 ................................................................................................................ 68
Nonregular languages.................................................................................................. 71
Lecture N0. 26 ................................................................................................................ 72
Pumping Lemma ......................................................................................................... 72
Lecture N0. 27 ................................................................................................................ 75
Pumping Lemma version II .......................................................................................... 75
Lecture N0. 28 ................................................................................................................ 77
Pseudo theorem .......................................................................................................... 78
Lecture N0. 29 ................................................................................................................ 79
Decidability................................................................................................................. 79
Determining whether the two languages are equivalent or not ? ................................... 80
Lecture N0. 30 ................................................................................................................ 83
Lecture N0. 31 ................................................................................................................ 87
Context Free Grammar (CFG) ...................................................................................... 87
CFG terminologies....................................................................................................... 87
Lecture N0. 32 ................................................................................................................ 90
Trees........................................................................................................................... 91
Lecture N0. 33 ................................................................................................................ 93
Polish Notation (o-o-o) ................................................................................................. 94
Lecture N0. 34 ................................................................................................................ 96
Total language tree...................................................................................................... 96
Regular Grammar ....................................................................................................... 97
Lecture N0. 35 ................................................................................................................ 99
Null Production ........................................................................................................... 99
Lecture N0. 36 .............................................................................................................. 102
Chomsky Normal Form (CNF) .................................................................................... 102
Lecture N0. 37 .............................................................................................................. 105
A new format for FAs ................................................................................................. 105
Lecture N0. 38 .............................................................................................................. 109
Nondeterministic PDA ............................................................................................... 111
Lecture N0. 39 .............................................................................................................. 114
PDA corresponding to CFG ........................................................................................ 114
Lecture N0. 40 .............................................................................................................. 118
Conversion form of PDA............................................................................................. 119
Lecture N0. 41 .............................................................................................................. 121
Lecture N0. 42 .............................................................................................................. 124
Lecture N0. 43 .............................................................................................................. 127
Non-Context-Free language ....................................................................................... 127
Pumping lemma for CFLs .......................................................................................... 128
Lecture N0. 44 .............................................................................................................. 133
Decidablity................................................................................................................ 133
Parsing Techniques ................................................................................................... 136
Lecture N0. 45 .............................................................................................................. 140
Turing machine......................................................................................................... 140
Last Updated: December 20, 2011
[Please see Errata if you have copy of handouts printed before this date]
2
© Copyright Virtual University of Pakistan
,Theory of Automata (CS402)
Theory of Automata
Lecture N0. 1
Reading Material
Introduction to Computer Theory Chapter 2
Summary
Introduction to the course title, Formal and In-formal languages, Alphabets, Strings, Null string, Words, Valid
and In-valid alphabets, length of a string, Reverse of a string, Defining languages, Descriptive definition of
languages, EQUAL, EVEN-EVEN, INTEGER, EVEN, { an bn}, { an bn an }, factorial, FACTORIAL,
DOUBLEFACTORIAL, SQUARE, DOUBLESQUARE, PRIME, PALINDROME.
What does automata mean?
It is the plural of automaton, and it means “something that works automatically”
Introduction to languages
There are two types of languages
• Formal Languages (Syntactic languages)
• Informal Languages (Semantic languages)
Alphabets
Definition
A finite non-empty set of symbols (called letters), is called an alphabet. It is denoted by Σ ( Greek letter sigma).
Example
Σ = {a,b}
Σ = {0,1} (important as this is the language which the computer understands.)
Σ = {i,j,k}
Note Certain version of language ALGOL has 113 letters.
Σ (alphabet) includes letters, digits and a variety of operators including sequential operators such as GOTO and
IF
Strings
Definition
Concatenation of finite number of letters from the alphabet is called a string.
Example
If Σ = {a,b} then
a, abab, aaabb, ababababababababab
Note
Empty string or null string
Sometimes a string with no symbol at all is used, denoted by (Small Greek letter Lambda) λ or (Capital Greek
letter Lambda) Λ, is called an empty string or null string.
The capital lambda will mostly be used to denote the empty string, in further discussion.
Words
Definition
Words are strings belonging to some language.
Example
If Σ= {x} then a language L can be defined as
L={xn : n=1,2,3,…..} or L={x,xx,xxx,….}
Here x,xx,… are the words of L
Note
3
© Copyright Virtual University of Pakistan
, Theory of Automata (CS402)
All words are strings, but not all strings are words.
Valid/In-valid alphabets
While defining an alphabet, an alphabet may contain letters consisting of group of symbols for example Σ1= {B,
aB, bab, d}.
Now consider an alphabet
Σ2= {B, Ba, bab, d} and a string BababB.
This string can be tokenized in two different ways
(Ba), (bab), (B)
(B), (abab), (B)
Which shows that the second group cannot be identified as a string, defined over
Σ = {a, b}.
As when this string is scanned by the compiler (Lexical Analyzer), first symbol B is identified as a letter
belonging to Σ, while for the second letter the lexical analyzer would not be able to identify, so while defining
an alphabet it should be kept in mind that ambiguity should not be created.
Remarks
While defining an alphabet of letters consisting of more than one symbols, no letter should be started with the
letter of the same alphabet i.e. one letter should not be the prefix of another. However, a letter may be ended in a
letter of same alphabet.
Conclusion
Σ1= {B, aB, bab, d}
Σ2= {B, Ba, bab, d}
Σ1 is a valid alphabet while Σ2 is an in-valid alphabet.
Length of Strings
Definition
The length of string s, denoted by |s|, is the number of letters in the string.
Example
Σ={a,b}
s=ababa
|s|=5
Example
Σ= {B, aB, bab, d}
s=BaBbabBd
Tokenizing=(B), (aB), (bab), (B), (d)
|s|=5
Reverse of a String
Definition
The reverse of a string s denoted by Rev(s) or sr, is obtained by writing the letters of s in reverse order.
Example
If s=abc is a string defined over Σ={a,b,c}
then Rev(s) or sr = cba
Example
Σ= {B, aB, bab, d}
s=BaBbabBd
Rev(s)=dBbabaBB
Defining Languages
The languages can be defined in different ways , such as Descriptive definition, Recursive definition, using
Regular Expressions(RE) and using Finite Automaton(FA) etc.
Descriptive definition of language
The language is defined, describing the conditions imposed on its words.
4
© Copyright Virtual University of Pakistan
