100%(1)100% found this document useful (1 vote) 157 views18 pagesTOC Notes
Hand written notes on toc
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content,
claim it here.
Available Formats
Download as PDF or read online on Scribd
Theory of Compulation
Intvoducion to Theosy of. Compubaton
Tntroduction te Finthe fudomota
[ Book: Lotveducheon Jo Theesy oF Compula-h on
- Michael Sipser
Tntesnahonal Student Edition
What is Compatahon 2
~ Malkplication of two numbers
~ Frading i ich onor:
yo word in a dictionary
> Checking whether there is a path between two Vertes
ina gtaeh:
Computafional devices * ,
£g. Calculator , Cellphone , Computer , pen and paper .
i + use,
Study Computational devices based on the vesouves that us
Finite Automata:
futon aka |
‘ta is the plural of ne word “auto mater”.
pubanato.
64 An electric switch
Scanned with CamScanner €g:2- Fan reguladow
Operabon: Cea CCA a§ ®
fx/xisa binary shing divisible by 4 ¢
Eg. Qe spw ss
Binary) Decimal
loo 4 a
1lo 6 x
1100 12 ee
Obsesve thatthe set of binary numbers divisible. by 4 are
etactly these thet hove 00 as & Sun ,
Start Blube : go
Accept State! 90
Scanned with CamScanner &q of Obtain
% Ilo x
LOG
°
bb 1100
Scanned with CamScanner Determinishe Finite Automaton CDFA)
Basie Meketon and Grvenhun, OFA Edit Lesson
Oefinihiors and Notations:
An alphabet is a finite set of symbols dendod by ¥ ox rf.
4 shing over an alphabet is a Sequence of symbols from
the alphabet.
eq? w= ollol
length of a stming \s the no of symbols in the stoing -clenoted
as \wl
eg: \onot| = 5,
The empty shing is the sting consistiag of O symbols.
denoted as E.
Zo e{ufuwa shing over ¥ and Iwl= ¢ t
ss { 00, ol, 10, n¥
Tes. ed!
(20
ae Uv xf
i7o
Language :
A language L over an alphabet 3, is a Subset of tah
& of & Finite automaton :
La fF wfw ends with e it
es
7 OP"
ie Cr
Oefinivion!
A deterministic finite automaton Cin short DFA) is 4
5 tuple Q,=,$, 40, F)
Where
Q is a firite set of Stales
X is the alphabet
§$:@xzOQts
lo € Q is the slosh state
F @
A zx
Le \ \
(State | symbol) Stake,
deden mi nteyic "
‘Whe 44 of Stales in a DFA Partitions the set of
al shoings
Sel of ie faite
Scanned with CamScanner
| Computation by OFA Regular Operahuns
Computation of a OFA.
lee = Caz, §) Fo) F) and lel W= 4,4)... ay
where a; € >
be say thet M accepks 0 if $F a sequence of sledles
Yor Sy My... tn Such trot
D Y= Gy Critral Congitton)
i ¢ Transi tien
Dy 28 O%,,a)) Wes beep Cees
1) %m € F Caccepk Condifion)
Note; The Glotes ¥; neal not be distinct.
Ut L ¢ =*
We say thd M accepts L
TE bes foext*/m accepls ot
ab 1 eos
we say thet Lis reguas if Sa OFA M such thet
L= Un)
by or { n zo} is not vegular
Exacoples:
4) uy = {w/o does not contdin I\ as a substring &
a
Lav
: of
Yo: Conteiin IN as a subs Slving
Jo: does Not contain il asa subshnog and does not end oth
9,: does not conten i] asa substangand it ends tae 4d
Scanned with CamScanner The state s a “damp stale!
A dump
de is a state fron where, The audomaton
aan not yeach an accep! state,
X= one
one yy tho Ly, Uys Lo
w- lel G01 41, 40,2,
L- - 100 Yo 1 40) So
On
44 is a dump state. ,
Regular Operations: lee arp ca >*
D Urien Operation
hop = fa/~xen oy xeBy
2D Concatenation Opesation ;
AB = t Hy] EN end Ye a4
also denoted as AP;
9: A= Labs o=f1,2,3, --.4
AB= Lal bl, az, bz, 03,53, CX ane
Scanned with CamScanner SD Star Operation :
Aa* = P y%-- ~My |r zo and % EA few all iy
é 2
g A= Lio, 001"
a* = [€, 10,00], lolo,
=
tooo], 00]] 0, e0l00)
Scanned with CamScanner Tintreduchon to Mede Nendetey minis m
Nendetes piinism *
from a stele 4 , 07 Gm input symbol a, the
Automaton car do to multiple states
k (ke o)
Com putteche > happens Simullentously aleng each of
these paths.
has € -4yansiions
af fheve ls a €- transition
» . ‘ ” +
then automaton moves to State 4) and a witha
sveading the next input bit
An input Ts accepted if theres some computation
path thet leads to an accept State , ~
Eg: dlondet Rite Automaton 0)
i
a Z) o, Gn) \
Ce Oo © : ay)
~ C40") > $405.93
(4,121 5
(4,,0) > {494
(4,, 2 T4323
. 2 . he
Note: The trarsitiwng ave labeled with symbols from I
Set
re EU Leh
Scanned with CamScanner Considew om input W= Clollo
{— Set of States the Bynes) fexd
| auto m: 6)
[ (
bt 4)
T4954, 20%
\ {20 40}
| £40,9,,9a, 48}
| £4041, 92, 20}
\ 1 40,40, det Tnput accepted
Concepts Covered:
Til now we hove Sencar model COFA); Which or a Sfate,
veadiag am input symbol Fron jnput shiag goesto single state.
Bat here we wil) see ci model which en Yeading a0 japut
symbol or not redding ang symbol at all , can go to maltiple,
skates.
Hence the model is called “ plondeteyministig, finites
automoka "
Scanned with CamScanner 13
NFA, definition and example
Th this leche we state the differences belucen NFA
and DFA. We also give firrmal defiailian of an NFA
and see some examples of Computation by a0 NEA Fer Shey
Differences bekoeen DFA and NFA:
OFA
(G2) 5 Single state | C4,0) > maltiple Stetes
Single computation _ multigle Gmputation
“N° € --tbransmihoens -have €- tansmition
“accept FF the Computation - accept if one of the compudativs
ends at an accept state .| paths ends at an accept State
* Rejected if the unique “Rejected TF non oF the computaticn
Gorm putation does nok paths ends at an accept State
ends atan accept Slate.
Definition: A non- deterministic finite automaton (NEA) is the
five tople Ne (4,2, 5, %,F).
Qiste Fisile Set of 6tetes
Zo is the input — alphabek
§: QxE—> 2%
Jo is The = hawk Gove
Fo is the acopk el of accepy Ghedes
Uv fet
for a cet A, 24 denofea the powes set of A,
Recatl thot Ze =
Scanned with CamScanner Defiaihon: We say nak N accepls an input Wwca, ay Ay
fF we can woe W AB W= hb), be
by whe
and Ta sequence of slates %,y,,
Sn Cro necessarily
dishiack) such drat
Y= 4, Cinitat condihion)
ii a .
Do 8 Cx 1 be) He 1,2,...m Chansihen eendinen)
"ye F
LON) =
iy t we =* [Nn accophs wt
¢ 2
§D ue fw efony* | 274 Jask symbol of wis @ L §
OST
@
Cacceplance Condom)
ville: fay ts te gy ts J doy, dek 9 fae.dys 22.
£304,933
Klolo:
;
$40} {40,49 25 $0,95 L> faa) 0}
ie
{90,448
Show that Joa Dra fire [.
it is Ut
= £6 fort * [the hth tagt | \
4D Lf we £03 [wl te divisible by 2 os by =}
Scanned with CamScanner
le Scanned with CamScanner Equivalence of NFA and DFA, Closuse Propest es
In this lechure we shoo the equivalerme of NFAand OFA by
Showing how to construct an equivalent OFA from a given NFA
We also discuss closuve pr
opesties of Yegular languages undes
the union, concatenatun and Star Operations
Every
OFA is alsoan NFA .
Theovens ; let ye
CQ, ZS, Io ,F) bean IFA then
there exists a DFA O- (a!
12,8! 4), F!) such that
LINng= L CD), 2
Gnshruchen of
. Q!' = 28
“tA €q@ ten §'(a,a)= U_ &(s,a)
1 ‘EA
Jo = £4,%
ae fa c@laare dt
bbhat about €- transitions 2,
let RL@
Define the E-closuse of Ras
Oox more.
© ~tramsifions J
Ece) = VU f4t[ tis reachable from ¥ usiag
TER
we define 8' te accomodate € - transitions
S(na= U ECS¢a))
YEN
Example
Le fw ford last eymbol in w is | +
rom (2 aC)
Scanned with CamScanner States
that ave not
wseochoble
lenown as dead states.
from the stest state ave,
Theevem: LF Ly and la ave yegular dren LULg, Li bo
and
«
Li ave also wegular,
Fora “regulor language we can assume thot there Is NFA
Acep ting iE witha unique accept state .
Longuage | NFA
Start State | accept State |
uy Ny 2) vy,
bo No Dee Vy
Lye lLCND
lo = Lin)
N
ey {2 TWN re
Y
Scanned with CamScanner Scanned with CamScanner
