Flat

1. 1
Theory of Automata
&
Formal Languages

2. 2
BOOKS
Theory of computer Science: K.L.P.Mishra &
N.Chandrasekharan
Intro to Automata theory, Formal languages and
computation: Ullman,Hopcroft
Motwani
Elements of theory of computation Lewis &
papadimitrou

3. 3
Syllabus
Introduction
Deterministic and non deterministic Finite
Automata, Regular Expression,Two way
finite automata,Finite automata with
output,properties of regular sets,pumping
lemma, closure properties,Myhill nerode
theorem

4. 4
Context free Grammar:Derivation
trees, Simplification forms
Pushdown automata:Def, Relationship
between PDA and context free
language,Properties, decision algorithms
Turing Machines:Turing machine
model,Modification of turing
machines,Church’s
thesis,Undecidability,Recursive and
recursively enumerable languages Post
correspondence problems recursive
functions

5. 5
Chomsky Hierarchy:Regular
grammars, unrestricted grammar, context
sensitive language, relationship among
languages

6. 6
CPU
input memory
output memory
Program memory
temporary memory

7. 7
CPU
input memory
output memory
Program memory
temporary memory3
)(xxf
computexx
computexx
2 2x 42*2z 82*)(zxf

8. 8
Automaton
CPU
input memory
output memory
Program memory
temporary memory
Automaton

9. 9
input memory
output memory
temporary memory
Finite
Automaton

10. 10
Different Kinds of Automata
Automata are distinguished by the temporary memory
•Finite Automata: no temporary memory
•Pushdown Automata: stack
•Turing Machines: random access memory

11. 11
input memory
output memory
Stack
Pushdown
Automaton
Pushdown Automaton
Programming Languages (medium computing power)
Push, Pop

12. 12
input memory
output memory
Random Access Memory
Turing
Machine
Turing Machine
Algorithms (highest computing power)

13. 13
Finite
Automata
Pushdown
Automata
Turing
Machine
Power of Automata

14. 14
Power sets
A power set is a set of sets
Powerset of S = the set of all the subsets of S
S = { a, b, c }
2
S
= { , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }
Observation:| 2
S
| = 2
|S|
( 8 = 2
3
)

15. 15
Cartesian Product
A = { 2, 4 } B = { 2, 3, 5 }
A X B = { (2, 2), (2, 3), (2, 5), ( 4, 2), (4, 3), (4, 4) }
|A X B| = |A| |B|
Generalizes to more than two sets
A X B X … X Z

16. 16
RELATIONS
R = {(x
1, y
1), (x
2, y
2), (x
3, y
3), …}
x
iR y
i
e. g. ifR = „>‟: 2 > 1, 3 > 2, 3 > 1
In relations x
ican be repeated

17. 17
Equivalence Relations
•Reflexive:x R x
•Symmetric:x R y y R x
•Transitive:x R Y andy R z x R z
Example:R = „=„
•x = x
•x = y y = x
•x = y andy = z x = z

18. 18
Equivalence Classes
For equivalence relationR
equivalence class ofx = {y : x R y}
Example:
R = { (1, 1), (2, 2), (1, 2), (2, 1),
(3, 3), (4, 4), (3, 4), (4, 3) }
Equivalence class of1 = {1, 2}
Equivalence class of3 = {3, 4}

19. 19
Example of Equivalence relation
Let Z = set of integers
R be defined on it as:
R= {(x,y)|x Z, y Z and
(x -y)is divisible by 5}
This relation is known as
”congruent modulo 5”

20. 20
The equivalence classes are
[0]
R= {…-10, -5, 0, 5,10,…}
[1]
R= {…..,-9, -4, 1, 6, 11, 16….}
[2]
R= {….-8, -3,2,7,12,17…..}
[3]
R= {….-7, -2, 3, 8 ,13,…}
[4]
R= {….-6,-1,4,9,14,19,….}
Z/R ={[0]
R, [1]
R, [2]
R, [3]
R, [4]
R}

21. 21
PROOF TECHNIQUES
•Proof by induction
•Proof by contradiction

22. 22
Induction
We have statementsP
1, P
2, P
3, …
If we know
•for some k that P
1, P
2, …, P
kare true
•for any n >= k that
P
1, P
2, …, P
nimply P
n+1
Then
Every P
iis true

23. 23
Trees
root
leaf
parent
child
Trees have no cycles

24. 24
Proof by Induction
•Inductive basis
Find P
1, P
2, …, P
kwhich are true
•Inductive hypothesis
Let‟s assume P
1, P
2, …, P
nare true,
for any n >= k
•Inductive step
Show that P
n+1is true

25. 25
root
leaf
Level 0
Level 1
Level 2
Level 3
Height 3

26. 26
Binary Trees

27. 27
Example
Theorem:A binary tree of height n
has at most 2
n
leaves.
Proof:
let l(i)be the number of leaves at level i
l(0) = 0
l(3) = 8

28. 28
Induction Step
hypothesis:l(n) <= 2
n
Level
n
n+1

29. 29
We want to show:l(i) <= 2
i
•Inductive basis
l(0) = 1 (the root node)
•Inductive hypothesis
Let‟s assume l(i) <= 2
i
for all i = 0, 1, …, n
•Induction step
we need to show that l(n + 1) <= 2
n+1

30. 30
hypothesis:l(n) <= 2
n
Level
n
n+1
l(n+1) <= 2 * l(n) <= 2 * 2
n
= 2
n+1
Induction Step

31. 31
Proof by Contradiction
We want to prove that a statement P is true
•we assume that P is false
•then we arrive at an incorrect conclusion
•therefore, statement P must be true

32. 32
Example
Theorem: is not rational
Proof:
Assume by contradiction that it is rational
= n/m
n and m have no common factors
We will show that this is impossible2 2

33. 33
= n/m 2 m
2
= n
2
Therefore, n
2
is even
n is even
n = 2 k
2 m
2
= 4k
2
m
2
= 2k
2
m is even
m = 2 p
Thus, m and n have common factor 2
Contradiction!2

34. 34
Basic Terms
Alphabet:A finite non empty set of elements.
={a,b,c,d,…z}

35. 35
•String:A sequence of letters
– Examples: “cat”, “dog”, “house”,…
– Defined over an alphabet:zcba ,,,,
Language:It is a set of strings on some
alphabet

36. 36
Alphabets and Strings
•We will use small alphabets:
•Strings abbaw
bbbaaav
abu ba, baaabbbaaba
baba
abba
ab
a

37. 37
String Operationsm
n
bbbv
aaaw


21
21 bbbaaa
abba mn
bbbaaawv 
2121
Concatenationabbabbbaaa

38. 38 12
aaaw
n
R
 n
aaaw 
21 ababaaabbb
Reversebbbaaababa

39. 39
String Length
•Length:
•Examples:n
aaaw 
21 nw 1
2
4
a
aa
abba

40. 40
Recursive Definition of Length
For any letter:
For any string :
Example:1a 1wwa wa 4
1111
111
11
1
a
ab
abbabba

41. 41
Length of Concatenation
•Example: vuuv 853
8
5,
3,
vuuv
aababaabuv
vabaabv
uaabu

42. 42
Proof of Concatenation Length
•Claim:
•Proof: By induction on the length
–Induction basis:
– From definition of length:vuuv v 1v vuuuv 1

43. 43
–Inductive hypothesis:
• for
–Inductive step: we will prove
–
– forvuuv nv ,,2,1 1nv vuuv

44. 44
Inductive Step
•Write , where
•From definition of length:
•From inductive hypothesis:
•Thus: wav 1,anw 1
1
wwa
uwuwauv wuuw vuwauwuuv 1

45. 45
Empty String
•A string with no letters:
•Observations: abbaabbaabba
www
0

46. 46
Substring
•Substring of string:
–a subsequence of consecutive characters
• String Substringbbab
b
abba
ab abbab
abbab
abbab
abbab

47. 47
Prefix and Suffix
•Prefixes Suffixesabbab abbab
abba
abb
ab
a b
ab
bab
bbab
abbab uvw
prefix
suffix

48. 48
Another Operation
•Example:
•Definition:
–

n
n
wwww abbaabbaabba
2 0
w 0
abba

49. 49
The * Operation
•: the set of all possible strings from
• alphabet
•* ,,,,,,,,,*
,
aabaaabbbaabaaba
ba

50. 50
The +Operation
: the set of all possible strings from
alphabet except ,,,,,,,,,*
,
aabaaabbbaabaaba
ba * ,,,,,,,, aabaaabbbaabaaba

51. 51
Language
•A language is any subset of
•Example:
•Languages:* ,,,,,,,,*
,
aaabbbaabaaba
ba },,,,,{
,,
aaaaaaabaababaabba
aabaaa

52. 52
Another Example
•An infinite language}0:{ nbaL
nn aaaaabbbbb
aabb
ab L Labb

53. 53
Operations on Languages
•The usual set operations
•Complement: aaaaaabbbaaaaaba
ababbbaaaaaba
aaaabbabaabbbaaaaaba
,,,,
}{,,,
},,,{,,,

 LL* ,,,,,,, aaabbabaabbaa

54. 54
Reverse
•Definition:
•Examples:}:{ LwwL
RR ababbaabababaaabab
R
,,,, }0:{
}0:{
nabL
nbaL
nnR
nn

55. 55
Concatenation
•Definition:
•Example: 2121 ,: LyLxxyLL baaabababaaabbaaaab
aabbaaba
,,,,,
,,,

56. 56
Another Operation
•Definition:
•Special case: 

n
n
LLLL bbbbbababbaaabbabaaabaaa
babababa
,,,,,,,
,,,,
3 0
0
,,aaabbaa
L

57. 57
More Examples
•}0:{ nbaL
nn }0,:{
2
mnbabaL
mmnn 2
Laabbaaabbb

58. 58
Star-Closure (Kleene *)
•Definition:
•Example:
• 
210
* LLLL ,,,,
,,,,
,,
,
*,
abbbbabbaaabbaaa
bbbbbbaabbaa
bba
bba

59. 59
Positive Closure
•Definition:*
21
L
LLL  ,,,,
,,,,
,,
,
abbbbabbaaabbaaa
bbbbbbaabbaa
bba
bba

60. 60
Finite Automaton
Input
String
•
Output
String
Finite
Automaton

61. 61
Finite Accepter
•
Input
“Accept”
or
“Reject”
String
Finite
Automaton
Output

62. 62
Transition Graph
•
initial
state
final
state
“accept”
state
transition
Abba -Finite Accepter0
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, ba,

63. 63
Initial Configuration
•1
q 2
q 3
q 4
q a b b a 5
q a a b b ba,
Input Stringa b b a ba, 0
q

64. 64
Reading the Input
•0
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, a b b a ba,

65. 650
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, a b b a ba,

66. 660
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, a b b a ba,

67. 670
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, a b b a ba,

68. 680
q 1
q 2
q 3
q 4
q a b b a
Output: “accept”5
q a a b b ba, a b b a ba,
Input finished

69. 69
Rejection
•1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, a b a ba, 0
q

70. 70
•0
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, a b a ba,

71. 71
•0
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, a b a ba,

72. 72
•0
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, a b a ba,

73. 730
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba,
Output:
“reject”a b a ba,
Input finished

74. 74
Another Examplea b ba, ba, 0
q 1
q 2
q a b a

75. 75a b ba, ba, 0
q 1
q 2
q a b a

76. 76a b ba, ba, 0
q 1
q 2
q a b a

77. 77a b ba, ba, 0
q 1
q 2
q a b a

78. 78a b ba, ba, 0
q 1
q 2
q a b a
Output: “accept”
Input finished

79. 79
Rejectiona b ba, ba, 0
q 1
q 2
q a b b

80. 80a b ba, ba, 0
q 1
q 2
q a b b

81. 81a b ba, ba, 0
q 1
q 2
q a b b

82. 82a b ba, ba, 0
q 1
q 2
q a b b

83. 83a b ba, ba, 0
q 1
q 2
q a b b
Output: “reject”
Input finished

84. 84
•Deterministic Finite Accepter (DFA)FqQM ,,,,
0 Q 0
q F
: Finite set of states
: input alphabet
: transition function
: initial state is a member of Q
: set of final states
:Q X Q

85. 85
Input Alphabet 0
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, ba, ba,

86. 86
Set of States Q 0
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, 543210
,,,,, qqqqqqQ ba,

87. 87
Initial State 0
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, ba, 0
q

88. 88
Set of Final StatesF 0
q 1
q 2
q 3
q a b b a 5
q a a b b ba, 4qF ba, 4
q

89. 89
Transition Function 0
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, QQ: ba,

90. 9010
,qaq 2
q 3
q 4
q a b b a 5
q a a b b ba, ba, 0
q 1
q

91. 9150
,qbq 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, ba, 0
q

92. 920
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, ba, 32
,qbq

93. 93
Transition Function
• 0
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, a b 0
q 1
q 2
q 3
q 4
q 5
q 1
q 5
q 5
q 2
q 2
q 3
q 4
q 5
q ba, 5
q 5
q 5
q 5
q

94. 94
Extended Transition Function * QQ*:* 0
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, ba,

95. 9520
,* qabq 3
q 4
q a b b a 5
q a a b b ba, ba, 0
q 1
q 2
q

96. 9640
,* qabbaq 0
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, ba,

97. 9750
,* qabbbaaq 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, ba, 0
q

98. 9850
,* qabbbaaq 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, ba, 0
q
Observation:There is a walk from to
with label0
q abbbaa 1
q

99. 99
Recursive Definition
•)),,(*(,*
,*
awqwaq
qq 0
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, ba,

100. 1000
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, ba, 2
1
0
0
0
0
,
,,
,,,*
),,(*
,*
q
bq
baq
baq
baq
abq

101. 101
Languages Accepted by DFAs
•Take DFA
•Definition:
–The language contains
–all input strings accepted by
– = { strings that drive to a final state} M ML M M ML

102. 102
Example
•0
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, ba, abbaML M
accept

103. 103
Another Example0
q 1
q 2
q 3
q 4
q a b b a 5
q a a b b ba, ba, abbaabML ,, M
acceptacceptaccept
•

104. 104
Formally
•For a DFA Language accepted by :FqQM ,,,,
0 M FwqwML ,*:*
0
alphabet
transition
function
initial
state
final
states

105. 105
Observation
•Language accepted by :
•Language rejected by :FwqwML ,*:*
0 M FwqwML ,*:*
0 M

106. 106
More Examples
•a b ba, ba, 0
q 1
q 2
q }0:{nbaML
n
accept trap state
or dead state

107. 107
•ML
= { all strings with prefix }ab a b ba, 0
q 1
q 2
q
acceptba, 3
q a b

108. 108
•ML
= { all strings without
substring }001 0 00 001 1 0 1 1 0 0 1,0

109. 109
Regular Languages
•A language is regular if there is
•a DFA such that
•All regular languages form a language
family
–L M MLL

110. 110
Example
•The language
•is regular:
•*,: bawawaL a b ba, a b b a 0
q 2
q 3
q 4
q

111. 111
Non Deterministic
Automata

112. 112
Non Deterministic Finite
AccepterFqQM ,,,,
0 :2
Q
Q

113. 1131q 2q 3
q a a a 0
q }{a
Alphabet =
Nondeterministic Finite Accepter (NFA)

114. 1141q 2q 3
q a a a 0
q
Two choices}{a
Alphabet =
Nondeterministic Finite Accepter (NFA)

115. 115
No transition1q 2q 3
q a a a 0
q
Two choices
No transition}{a
Alphabet =
Nondeterministic Finite Accepter (NFA)

116. 116a a 0
q 1q 2q 3
q a a
First Choicea

117. 117a a 0
q 1q 2q 3
q a a a
First Choice

118. 118a a 0
q 1q 2q 3
q a a
First Choicea

119. 119a a 0
q 1q 2q 3
q a a a
“accept”
First Choice
All input is consumed

120. 120a a 0
q 1q 2q 3
q a a
Second Choicea

121. 121a a 0
q 1q 2q a a
Second Choicea 3
q

122. 122a a 0
q 1q 2q a a a 3
q
Second Choice
No transition:
the automaton hangs

123. 123a a 0
q 1q 2q a a a 3
q
Second Choice
“reject”
Input cannot be consumed

124. 124
An NFA accepts a string:
when there is a computationof the NFA
that accepts the string
•All the input is consumed and the automaton
is in a final state

125. 125
An NFA rejects a string:
when there is no computation of the NFA
that accepts the string
•All the input is consumed and the
automaton is in a non final state
•The input cannot be consumed

126. 126
Exampleaa
is accepted by the NFA:0
q 1q 2q 3
q a a a
“accept”0
q 1q 2q a a a 3
q
“reject”
because this computation
accepts aa

127. 127a 0
q 1q 2q 3
q a a
Rejection examplea

128. 128a 0
q 1q 2q 3
q a a a
First Choice

129. 129a 0
q 1q 2q 3
q a a a
First Choice
“reject”

130. 130
Second Choicea 0
q 1q 2q 3
q a a a

131. 131
Second Choicea 0
q 1q 2q a a a 3
q

132. 132
Second Choicea 0
q 1q 2q a a a 3
q
“reject”

133. 133
Examplea
is rejected by the NFA:0
q 1q 2q a a a 3
q
“reject”0
q 1q 2q a a a 3
q
“reject”
All possible computations lead to rejection

134. 134
Rejection examplea a 0
q 1q 2q 3
q a a a a

135. 135a a 0
q 1q 2q 3
q a a a
First Choicea

136. 136a a 0
q 1q 2q 3
q a a
First Choicea a
No transition:
the automaton hangs

137. 137a a 0
q 1q 2q 3
q a a a
“reject”
First Choicea
Input cannot be consumed

138. 138a a 0
q 1q 2q 3
q a a
Second Choicea a

139. 139a a 0
q 1q 2q a a
Second Choicea 3
q a

140. 140a a 0
q 1q 2q a a a 3
q
Second Choice
No transition:
the automaton hangsa

141. 141a a 0
q 1q 2q a a a 3
q
Second Choice
“reject”a
Input cannot be consumed

142. 142aaa
is rejected by the NFA:0
q 1q 2q 3
q a a a
“reject”0
q 1q 2q a a a 3
q
“reject”
All possible computations lead to rejection

143. 1431q 2q 3
q a a a 0
q
Language accepted:}{aaL

144. 144
Lambda →Transitions1q 3
q a 0
q 2q a

145. 145a a 1q 3
q a 0
q 2q a

146. 146a a 1q 3
q a 0
q 2q a

147. 147a a 1q 3
q a 0
q 2q a
(read head doesn‟t move)

148. 148a a 1q 3
q a 0
q 2q a

149. 149a a 1q 3
q a 0
q 2q a
“accept”
String is acceptedaa
all input is consumed

150. 150a a 1q 3
q a 0
q 2q a
Rejection Examplea

151. 151a a 1q 3
q a 0
q 2q a a

152. 152a a 1q 3
q a 0
q 2q a
(read head doesn‟t move)a

153. 153a a 1q 3
q a 0
q 2q a a
No transition:
the automaton hangs

154. 154a a 1q 3
q a 0
q 2q a
“reject”
String is rejectedaaa a
Input cannot be consumed

155. 155
Language accepted:}{aaL 1q 3
q a 0
q 2q a

156. 156
Another NFA Example0
q 1q 2q a b 3
q

157. 157a b 0
q 1q 2q a b 3
q

158. 1580
q 2q a b 3
q a b 1q

159. 159a b 0
q 1q a b 3
q 2q

160. 160a b 0
q 1q a b 3
q 2q
“accept”

161. 1610
q a b a b
Another Stringa b 1q 2q 3
q

162. 1620
q a b a b a b 1q 2q 3
q

163. 1630
q a b a b a b 1q 2q 3
q

164. 1640
q a b a b a b 1q 2q 3
q

165. 1650
q a b a b a b 1q 2q 3
q

166. 1660
q a b a b a b 1q 2q 3
q

167. 1670
q a b a b a b 1q 2q 3
q

168. 168a b a b 0
q a b 1q 2q 3
q
“accept”

169. 169ab
ababababababL ...,,,
Language accepted0
q 1q 2q a b 3
q

170. 170
Another NFA Example0
q 1q 2q 0 1 1,0

171. 171{ }
{}*10=
...,101010,1010,10,λ=)(ML 0
q 1q 2q 0 1 1,0
Language accepted

172. 172
Remarks:
•The symbol never appears on the
input tape 0
q 2M 0
q 1M {}=)M(L
1 }λ{=)M(L
2
•Extreme automata:

173. 1730q 2q 1q a 0q 1q a }{=)(
1aML 2M 1M }{=)(
2aML
NFA DFA
•NFAs are interesting because we can
express languages easier than DFAs
b
a,b
a,b

174. 174
Formal Definition of NFAsFqQM ,,,,
0 :Q : :
0
q :F
Set of states, i.e.210
,,qqq :
Input alphabet, i.e.ba,
Transition function
Initial state
Final states

175. 17510
1,qq 0 1 1,0
Transition Function 0
q 1q 2q

176. 1760
q 0 1 1,0 },{)0,(
201
qqq 1q 2q

177. 1770
q 0 1 1,0 1q 2q },{),(
200
qqq

178. 1780
q 0 1 1,0 1q 2q )1,(
2q

179. 179
Extended Transition Function
•* 0q 5q 4q 3q 2q 1q a a a b 10
,* qaq

180. 180540
,,* qqaaq 0q 5q 4q 3q 2q 1q a a a b

181. 1810320
,,,* qqqabq 0q 5q 4q 3q 2q 1q a a a b

182. 182
Formallywqq
ij
,*
It holds
if and only if
there is a walk from to
with label i
q j
q w

183. 183
The Language of an NFA
•0q 5q 4q 3q 2q 1q a a a b 540 ,,* qqaaq M )(MLaa 50
,qqF

184. 1840q 5q 4q 3q 2q 1q a a a b 0320 ,,,* qqqabq MLab 50
,qqF

185. 185
•0q 5q 4q 3q 2q 1q a a a b 50
,qqF 540 ,,* qqabaaq )(MLaaba

186. 1860q 5q 4q 3q 2q 1q a a a b 50
,qqF 10
,* qabaq MLaba

187. 1870q 5q 4q 3q 2q 1q a a a b aaababaaML *

188. 188
Formally
•The language accepted by NFA is:
•where
•and there is some M ,...,,
321
wwwML ,...},{),(*
0 jim
qqwq Fq
k (final state)

189. 189
•0q kq w w w ),(*
0
wq MLw Fq
k iq jq

190. 190
Equivalence of NFAs and DFAs

191. 191
Equivalence of Machines
•For DFAs or NFAs:
•Machine is equivalent to machine
•if
•1M 2M 21 MLML

192. 192
•0q 1q 2q 0 1 1,0 0q 1q 2q 0 1 1 0 1,0
NFA
DFA*}10{
1ML *}10{
2ML 1M 2M

193. 193
•Since
•machines and are equivalent *10
21 MLML 1M 2M 0q 1q 2q 0 1 1,0 0q 1q 2q 0 1 1 0 1,0
DFA
NFA1M 2M

194. 194
Equivalence of NFAs and DFAs
Question: NFAs =DFAs ?
Same power?
Accept the same languages?

195. 195
Equivalence of NFAs and DFAs
Question: NFAs =DFAs ?
Same power?
Accept the same languages?
YES!

196. 196
We will prove:
Languages
accepted
by NFAs
Languages
accepted
by DFAs
NFAs and DFAs have the same
computation power

197. 197
Languages
accepted
by NFAs
Languages
accepted
by DFAs
Step 1
Proof:Every DFA is trivially an NFA
A language accepted by a DFA
is also accepted by an NFA

198. 198
Languages
accepted
by NFAs
Languages
accepted
by DFAs
Step 2
Proof:Any NFA can be converted to an
equivalent DFA
A language accepted by an NFA
is also accepted by a DFA

199. 199
NFA to DFA
•a b a 0q 1q 2q
NFA
DFA0q M M

200. 200
•a b a 0q 1q 2q
NFA
DFA0q 21,qq a M M

201. 201
•a b a 0q 1q 2q
NFA
DFA0q 21,qq a b M M

202. 202
•a b a 0q 1q 2q
NFA
DFA0q 21,qq a b a M M

203. 203
•a b a 0q 1q 2q
NFA
DFA0q 21,qq a b a b M M

204. 204
•a b a 0q 1q 2q
NFA
DFA0q 21,qq a b a b ba, M M

205. 205
•a b a 0q 1q 2q
NFA
DFA0q 21,qq a b a b ba, M M )(MLML

206. 206
NFA to DFA: Remarks
•We are given an NFA
•We want to convert it to an equivalent DFAM M )(MLML

207. 207
•If the NFA has states
•the DFA has states in the power set
•,...,,
210
qqq ,....,,,,,,,
7432110
qqqqqqq

208. 208
Procedure NFA to DFA
•
•1.Initial state of NFA:
•
•Initial state of DFA: 0
q 0
q

209. 209
•a b a 0q 1q 2q
NFA
DFA0q M M

210. 210
Procedure NFA to DFA
•2.For every DFA’s state
• Compute in the NFA
•
• Add transition to DFA},...,,{
mji
qqq ...
,,*
,,*
aq
aq
j
i },...,,{
mji
qqq },...,,{},,...,,{
mjimji
qqqaqqq

211. 211
•a b a 0q 1q 2q
NFA0q 21,qq a
DFA},{),(*
210 qqaq 210 ,, qqaq M M },{),(*
210 qqaq

212. 212
Procedure NFA to DFA
•Repeat Step 2for all letters in alphabet,
• until
•no more transitions can be added.

213. 213
•a b a 0q 1q 2q
NFA
DFA0q 21,qq a b a b ba, M M

214. 214
Procedure NFA to DFA
•3.For any DFA state
• If some is a final state in the NFA
• Then,
• is a final state in the DFA
•},...,,{
mji
qqq j
q },...,,{
mji
qqq

215. 215
•a b a 0q 1q 2q
NFA
DFA0q 21,qq a b a b ba, Fq
1 Fqq
21, M M

216. 216
Theorem
•
Take NFAM
Apply procedure to obtain DFA M
Then and are equivalent :M M MLML

217. 217
Finally
We have proven
Languages
accepted
by NFAs
Languages
accepted
by DFAs

218. 218
Languages
accepted
by NFAs
Languages
accepted
by DFAs
We have proven
Regular Languages

219. 219
Languages
accepted
by NFAs
Languages
accepted
by DFAs
We have proven
Regular LanguagesRegular Languages

220. 220
Languages
accepted
by NFAs
Languages
accepted
by DFAs
We have proven
Regular LanguagesRegular Languages
Thus, NFAs accept the regular languages

221. 221
Single Final State
for NFAs and DFAs

222. 222
Observation
•Any Finite Automaton (NFA or DFA)
•can be converted to an equivalent NFA
•with a single final state

223. 223a b b a
NFA
Equivalent NFA a b b a
Example

224. 224
NFA
In General
Equivalent NFA
Single
final state

225. 225
Extreme Case
NFA without final state
Add a final state
Without transitions

226. 226
Some Properties of
Regular Languages

227. 2271L 2L 21LL
Concatenation:*
1L
Star:21LL
Union:
Are regular
Languages
For regular languages and
we will prove that:
properties

228. 228
We Say:
Regular languages are closed under21LL
Concatenation:*
1L
Star:21LL
Union:

229. 229
Properties1L 2L 21LL
Concatenation:*
1L
Star:21LL
Union:
Are regular
Languages
For regular languages and
we will prove that:

230. 2301L
Regular language11LML 1M
Single final state
NFA2M 2L
Single final state22LML
Regular language
NFA

231. 231
Example}{
1
baL
n a b 1M baL
2 a b 2M

232. 232
Union
•NFA for 1M 2M 21LL

233. 233
•a b a b }{
1
baL
n }{
2baL }{}{
21
babaLL
n
NFA for

234. 234
Concatenation
•NFA for 21LL 1M 2M

235. 235
Example
•
•NFA fora b a b }{
1
baL
n }{
2baL }{}}{{
21
bbaababaLL
nn

236. 236
Star Operation
•NFA for *
1L 1M *
1L

237. 237
Example
•NFA for*}{*
1
baL
n a b }{
1
baL
n
N>= 0

238. 238
Procedure: NFA to DFA
1Create a graph with vertex {q0}.Identify this vertex as
initial vertex of DFA.
2Repeat the following steps until no more edges are
missing.Take any vertex {qi,qj,….qk} of G that has no
outgoing edge for some symbol a of the alphabet.
Compute (qi, a), (qj, a)…. (qk, a)
Then form the union of all these yielding the set
{ql, qm, …qn}.
Create a vertex for G labeled {ql, qm,…qn} if it does not
already exist.
Add to G an edge from {qi, qj,…qk} to {ql,qm…qn} and
label it with a.
3Every state of G whose label contains any qf of F is
identified as a final vertex of DFA.
4If NFA accepts then vertex {q0} in G is also made a
final vertex.* * * *

239. 239
q0
q2
q1
0,1 0,1
1
0

240. 240
q0
{q0,
q1}
q
1
q0,q1,q2
q1,q2
q2
0
0
1
1
0
0,1
0,1
1
1
0,1
Equivalent
DFA
Start
0