RAJALAKSHMI ENGINEERING COLLEGE
6/7/2012
UNIT- I
AUTOMATA
6/7/2012
6/7/2012
6/7/2012
6/7/2012
6/7/2012
6/7/2012
6/7/2012
6/7/2012
6/7/2012
10
6/7/2012
11
6/7/2012
12
6/7/2012
13
6/7/2012
14
Finite Automata
6/7/2012
15
6/7/2012
16
States Open Closed Sensors Front Someone on the Front pad Rear Someone on the Rear pad Both Someone on both the pads Neither No one on either pad
6/7/2012
17
6/7/2012
18
6/7/2012
19
6/7/2012
20
6/7/2012
21
6/7/2012
22
6/7/2012
23
6/7/2012
24
6/7/2012
25
6/7/2012
26
6/7/2012
27
6/7/2012
28
6/7/2012
29
6/7/2012
30
6/7/2012
31
6/7/2012
32
6/7/2012
33
6/7/2012
34
6/7/2012
35
6/7/2012
36
6/7/2012
37
6/7/2012
38
6/7/2012
39
6/7/2012
40
UNIT - II
REGULAR EXPRESSIONS AND LANGUAGES
6/7/2012
41
6/7/2012
42
6/7/2012
43
6/7/2012
44
6/7/2012
45
6/7/2012
46
6/7/2012
47
6/7/2012
48
6/7/2012
49
6/7/2012
50
6/7/2012
51
6/7/2012
52
6/7/2012
53
6/7/2012
54
6/7/2012
55
6/7/2012
56
6/7/2012
57
6/7/2012
58
6/7/2012
59
6/7/2012
60
6/7/2012
61
6/7/2012
62
6/7/2012
63
6/7/2012
64
6/7/2012
65
6/7/2012
66
6/7/2012
67
6/7/2012
68
6/7/2012
69
6/7/2012
70
6/7/2012
71
6/7/2012
72
6/7/2012
73
6/7/2012
74
6/7/2012
75
6/7/2012
76
6/7/2012
77
6/7/2012
78
6/7/2012
79
Questions about Regular Languages
6/7/2012
80
Question contd
6/7/2012
81
Singleton Languages are Regular
6/7/2012
82
Finite Languages are regular
6/7/2012
83
6/7/2012
84
6/7/2012
85
6/7/2012
86
6/7/2012
87
6/7/2012
88
Closure Properties for Regular Languages
6/7/2012
89
Myhill-Nerode Theorem
6/7/2012
90
6/7/2012
91
6/7/2012
92
6/7/2012
93
UNIT III
CONTEXT-FREE GRAMMAR AND LANGUAGES
6/7/2012
94
Context Free Grammars
6/7/2012
95
Cont
6/7/2012
96
Cont
6/7/2012
97
Defining CFG
6/7/2012
98
Notational conventions For CFGs
6/7/2012
99
OTHER CFG EXAMPLES
6/7/2012
100
Languages of CFG
6/7/2012
101
Languages of CFG
6/7/2012
102
Regular Languages and CFL
6/7/2012
103
Translating FAs into CFG
6/7/2012
104
Formalizing the Translation
6/7/2012
105
Closure Properties of CFL
6/7/2012
106
Proving CFLs closed under Union
6/7/2012
107
IDEA
6/7/2012
108
Formal Construction of Gu
6/7/2012
109
Derivations
6/7/2012
110
Sentential Form
6/7/2012
111
Left Most and Right Most Derivation
6/7/2012
112
Right-Linear Grammars
6/7/2012
113
Ambiguous Grammars
6/7/2012
114
Ambiguous Grammars
6/7/2012
115
Pushdown Automata
Recall our study of regular languages. They were defined in terms of regular expressions (syntax). We then showed that FAs provide the computational power needed to process them. We would like to mimic this line of development for CFLs. We have a syntactic definition of CFLs in terms of CFGs. What kind of computing power is needed to process (i.e. recognize) CFLs? Do FAs suffice?
6/7/2012
116
Cont
6/7/2012
117
Cont
6/7/2012
118
Example PDA
n n for{0 1 |n0}
6/7/2012
119
Formal Definition
6/7/2012
120
Instantaneous Description
6/7/2012
121
Language accepted by PDA
6/7/2012
122
Language accepted by PDA
6/7/2012
123
Language accepted by PDA
6/7/2012
124
Equivalence of CFGs and PDAs
6/7/2012
125
Cont
6/7/2012
126
Deterministic PDA
6/7/2012
127
UNIT - IV
PROPERTIES OF CONTEXT-FREE LANGUAGES
6/7/2012
128
Chomsky Normal Form
6/7/2012
129
Defining CNF
6/7/2012
130
What is the Big Deal about CNF?
6/7/2012
131
Cont
6/7/2012
132
Converting CFGs into CNF
6/7/2012
133
Eliminating -Productions
6/7/2012
134
Cont
6/7/2012
135
Cont
6/7/2012
136
Nullability
6/7/2012
137
Generating an -Production-free CFGs
6/7/2012
138
Converting CFGs into CNF
6/7/2012
139
Eliminating Unit Productions
6/7/2012
140
Cont
6/7/2012
141
U(G,A) and New Productions
6/7/2012
142
Example
6/7/2012
143
Cont
6/7/2012
144
Formal Construction
6/7/2012
145
Eliminating Terminal Productions
6/7/2012
146
Example
6/7/2012
147
Formal Construction
6/7/2012
148
Pumping Lemma For CFLs
6/7/2012
149
Cont
6/7/2012
150
Derivation Trees
6/7/2012
151
Defining Derivation Tree
6/7/2012
152
Example
6/7/2012
153
Derivation Trees and CNF
6/7/2012
154
6/7/2012
155
Pumping Lemma for CFL
6/7/2012
156
Proving Languages Non Context Free using Pumping Lemma
6/7/2012
157
Prove that L= {aNbNcN|N 0} is Not a CFL
6/7/2012
158
Proof Cont
6/7/2012
159
Turing Machines
6/7/2012
160
A Finite Automaton
6/7/2012
161
A Pushdown Automaton
6/7/2012
162
A Turing Machine
6/7/2012
163
Cont..
6/7/2012
164
Differences
6/7/2012
165
Example
6/7/2012
166
Cont
6/7/2012
167
Cont
6/7/2012
168
Cont
6/7/2012
169
Formal Definition
6/7/2012
170
Cont..
6/7/2012
171
Cont
6/7/2012
172
Cont
6/7/2012
173
Configurations
6/7/2012
174
Cont
6/7/2012
175
More Configuration
6/7/2012
176
Accepting a Language
6/7/2012
177
Enumerable Languages
6/7/2012
178
UNIT V
UNDECIDABILITY
6/7/2012
179
Enumerable Languages
6/7/2012
180
Enumerable Languages
6/7/2012
181
Example
6/7/2012
182
Example
6/7/2012
183
Example
6/7/2012
184
Element Distinctness
6/7/2012
185
Element Distinctness
6/7/2012
186
Element Distinctness
6/7/2012
187
Element Distinctness
6/7/2012
188
Element Distinctness
6/7/2012
189
Variants
6/7/2012
190
Multitape Turing Machine
6/7/2012
191
Equivalence
6/7/2012
192
Simulation
6/7/2012
193
Simulation
6/7/2012
194
Non Deterministic Turing Machine
6/7/2012
195
Decidability
6/7/2012
196
Example
6/7/2012
197
Theorem
6/7/2012
198
Theorem
6/7/2012
199
Theorem
6/7/2012
200
Theorem
6/7/2012
201
Halting Problem
6/7/2012
202
Cont..
6/7/2012
203
Cont..
6/7/2012
204
Turing Machines are countable
6/7/2012
205
Cont..
6/7/2012
206
Post Correspondence Problem
6/7/2012
207
Cont
6/7/2012
208
Cont...
6/7/2012
209
Cont
6/7/2012
210
Cont
6/7/2012
211
Cont
6/7/2012
212
6/7/2012
213
NP-complete Problem
6/7/2012
214
6/7/2012
215
6/7/2012
216
Decision Problems To keep things simple, we will mainly concern ourselves with decision problems. These problems only require a single bit output: ``yes'' and ``no''. How would you solve the following decision problems?
Is this directed graph acyclic? Is there a spanning tree of this undirected graph with total weight less than w? Does this bipartite graph have a perfect (all nodes matched) matching? Does the pattern p appear as a substring in text t?
6/7/2012 217
6/7/2012
218
P P is the set of decision problems that can be solved in worst-case polynomial time: If the input is of size n, the running time must be O(nk). Note that k can depend on the problem class, but not the particular instance. All the decision problems mentioned above are in P.
6/7/2012
219
Nice Puzzle
The class NP (meaning non-deterministic polynomial time) is the set of problems that might appear in a puzzle magazine: ``Nice puzzle.'' What makes these problems special is that they might be hard to solve, but a short answer can always be printed in the back, and it is easy to see that the answer is correct once you see it. Example... Does matrix A have an LU decomposition?
No guarantee if answer is ``no''.
6/7/2012
220
6/7/2012
221
NP Technically speaking:
A problem is in NP if it has a short accepting certificate. An accepting certificate is something that we can use to quickly show that the answer is ``yes'' (if it is yes). Quickly means in polynomial time. Short means polynomial size.
This means that all problems in P are in NP (since we don't even need a certificate to quickly show the answer is ``yes''). But other problems in NP may not be in P. Given an integer x, is it composite? How do we know this is in NP?
6/7/2012 222
Good Guessing Another way of thinking of NP is it is the set of problems that can solved efficiently by a really good guesser. The guesser essentially picks the accepting certificate out of the air (Non-deterministic Polynomial time). It can then convince itself that it is correct using a polynomial time algorithm. (Like a right-brain, left-brain sort of thing.) Clearly this isn't a practically useful characterization: how could we build such a machine?
6/7/2012
223
Exponential Upperbound Another useful property of the class NP is that all NP problems can be solved in exponential time (EXP). This is because we can always list out all short certificates in exponential time and check all O(2nk) of them. Thus, P is in NP, and NP is in EXP. Although we know that P is not equal to EXP, it is possible that NP = P, or EXP, or neither. Frustrating!
6/7/2012
224
NP-hardness As we will see, some problems are at least as hard to solve as any problem in NP. We call such problems NP-hard. How might we argue that problem X is at least as hard (to within a polynomial factor) as problem Y? If X is at least as hard as Y, how would we expect an algorithm that is able to solve X to behave?
6/7/2012
225
6/7/2012
226
6/7/2012
227
6/7/2012
228
6/7/2012
229
NP
co-NP
P
One of the central (and widely and intensively studied 30 years) problems of (theoretical) computer science is to prove that (a) PNP (b) NP co-NP. All evidence indicates that these conjectures are true. Disproving any of these two conjectures would not only be considered truly spectacular, but would also come as a tremendous surprise (with a variety of far-reaching counterintuitive consequences). NP-complete: Collection Z of problems is NP-complete if (a) it is NP and (b) if polynomial-time algorithm existed for solving problems in Z, then P=NP.
6/7/2012 230
6/7/2012
231
6/7/2012
232
6/7/2012
233
6/7/2012
234
6/7/2012
235
NP-Complete Problems
6/7/2012
236
6/7/2012
237
6/7/2012
238
6/7/2012
239
6/7/2012
240
6/7/2012
241
6/7/2012
242
