Ut: — Basic Concept & Automata Theory Automation: a systems where energy waterils and information are Lransformecd, Lranemitted cond used fer performing Some function without oltrect particibatton of human Exambtes- Automate Resign Machine ofp Inputi- at each of desorete instance of time T; Treeta. | the input value Ty, T).Tye--- Ta. each of which = con take fintte no. of fired value fron arput olphaber. Output:~ Op, Op ---- O, are the output of model each’ of which can take finite no of valreos from putput 0. = Skate!- Nest state of an automatum ot on ine instant - 3 of time f& determine by present and present frput +State Relation Next state of an automatun at ans Enstont of time £s detorméne by present state anol present snput. Output Relatio:- Output fs related either ctate ony or 40 boty frput and state» Finite Automata int mata abut Finite Autos a WEBS Outpub PFA NEA B-NFEA Moore, abet, Mocktne Machine Finite Autometat— Tt hos sot of states and ite controb mene frow state to state in responce to ercternal snput. Fintte Automate witheut 6 Apt: * 2" Dea ( Boterministic Finite Automate A finite automatinm can be represented: he 6° Auptes Q@,=.6- Ws F- lherey | is Finite ren-empte get of states"y g Ls finite. non ember set of fnput alphabet. 6 fs transition Functor which moths (Oxy) into Q and. J direct frensition function. Yo fs Enitial State 16 @ F Zs sub-set of @» F xs set of Firal otates ( there may be more, than one fina tats). Auaxtion@)s- Basign, a DFA S(o,L) fer Aorguage: | accepting oll otras Starts ult 0. at ony Enatant of Line the automation con be by one of Ww states 199% »---Tn- i = {o, 000, 001, OO1DL ---} PUeee sere eee edd UCU eT lal 0 rT rm& Contruct 0 OFA He e tet accept set of alk string, sv Z={OLt every atriy wtantel ol Soft is {o- 00. O10 0110, o1010, oLors0f Qe Construct ® DEA with set of ot’ ehdtrg with 0- ye {ott 7 ¢ Lz {0 ,00, 100, 110, O10, t1o0; ox Lor--- df 0 cP t Co) ie @) Qe odLol ok Hi & aia ——s se RRPORRR RR ARM wean annn i __ -> Ques :- Le [or by Star kira with a andl ange wily by & - fob, aab,aacb, abbb, a-..-- b 7 i } Trorkition table b > ee G& Uy a Ve ca de 3 Ques: Besign o DAA that exeept ale string ever 9 Le {or} «is Length of ) G) (We & ‘String > ab jw <2 | * ro. =p Sl sy Le fab, am 4 = ba, bb 3 ~ =» =» == =— =3 2 =3 = UCUL=fott » Starting ond ending lity different seymbod L= fot, 10, oL0t , Loto ___. } : Qa % Ee fOd} starting and ending with orm symbol. OL “4 ¢ be foe. Lt, OL0L0, {0104 bal ; M4 Rentgr 0 OFA over Lz fab] uch that org atrtng aceepted must Start ult. aa or bb. he [an bb, @ab, bba, aba ———.} Aaa. bbb ° LAPP P PNA ARMM MMM OM mam mn -° J 5% d HEADY a} } 1 aH , J Must Rowe aa or bb he { an, bbs aob, abba » baab ~~~ fends uth an or bb Le {ans AOn » bap 3 baw -—~ uf bb , Obb + bbb + Non- Beterministic Finite Automata (NFA): VA Finite automatum can be represintid by 5 tuples Q.2, 6. de. F Where Q. fs finite non-empty gut of States Ls findte none embry sit of dnput alphabet & is transkttm function with maths (ax) ano 2s urine direct trantitton function: 2 4, us dnittal state 4 68 fF £8 sub + sof of O. Fides Set of Frab atates( thore moony be more thor one final state). > aH eRe ew PPppnebuos- Resign @ NPA tk vere ne must starts ulsho. r —) mS = a) xefot} “3 he {o, ot, of tt---~-f =3 =9 © >, ~ © =3 “3S Ending wit 1. ae = heft, OL, 00L, DOLL, Lozoo,——- a my : ==9 oO, _ ° —=3 (1) f > fo de Got ~ Must Rave 0. @}~ ~ - hefo Qos ; 2 0 ==3 al 3 ey PR lt 2 % 4% ~=3 Cottruct NEA accepting the etring Ey, ( =f{0t} where — > nd tout symbok cs V4, 0 Tony —=9 ——y d= [£0 010, 1 _| oo ft sy 41 >} 40 tend —? pt 4] a te ° O——@)—4 @. - Construct a NPA willl exactly Longe of tuco uihere Letay Af TUGuat Corstruct ao NPA that accebt ate string. over- fort} Where w Stort with o1 ad Cmtain ot di) Rnd with 00 WM stort with Of A= {Oly O10, O41, o144.-..7 (&) o @) fi. Or WW Ogntain ot A= {ow oto, oot, dott ~—f OQ —(f§— @ 7 Ort. ay End with 60 t= fo0,100, 000, t100~-— } a PHM HMMA Ame 9 !Transition Tables Besign a DRA Refor} ops he f w]e pus even not of- 0's Even no. of 1's. k= { 00, oro] ti .. - 4} WhyEven no of 0's k odd no. of {'s 421 00,1, Ovi , OVI , 010, ;o108-~~ f 2 De a _ > Odd no: of-d's b odd no of t's nef eb, Cll! Cstruct » DPA E=fab} Bhat query otrtrg acetpe socond syrebdl ss a ond foarte Mymbol Le b fm given languages ; aabb» boubb ~-- ~ } 04 Ay ddd? A Ta AnD nTConvert DFA Equivalence tuto NRA Ee{arb} Contain obb Ae [obb: aabb, abbw,-— ~-- f , 2 Qa CQ Qos ‘ (ho Gb 8 6 Abuses o L > Yo UY Ml] A Gott Consider wo giver jporsition table, emstruct a deterministic Findte automaton , equtvatent (8. Fa & , % ) met faesayp otf s 6) de te) IARAANAAAARAMR ARAMA AM DR Be ” T n AAT ILuhtre 6 26 define by stab table/ transition table The stater are sub-set of Aidit bes be , dot qe ds tre initial State , 4, and Got, ave Ane ferabstoto. 8 ts defined by The Sate stable © L (401 [tJ fy [2041] (aoa Bots] HULA HR fodedure 2 A DEA can simulate the boknw'our 3 OF NDEA by Increasing Bre no, of Sintes (A DPA 8.3.6, Gos) Caw be Weured os an NOAA ie, 6, 4.6) by define s(t.) = {560.0}° NDEA sis a more generat machine without bere Powers 1 sbhs | dures ffir o OPA equivalent to M = (4 hig forrh , Ss 40542} where & i givon oY “9AM HA BO aw oa 409, 34 PAAANRP ODMH HDS 4{ors Ve GU V4) VU, ° Lose V9 Ty 11409. Lot) a 4) byAANXVANVV ADE ate wwe Minimizotion of DFA. ANVIL iow of _[o.. Construction of Minimum 2-By definition of Me ~ enone b Constrckion ef feo re= fal as e} a 1s Sat of all fidl stote » OP tvs rot final state = as Q= A-Ay, =— Construction of Teg From Me g- hot &* bo subcot fn Te, Jf Grand Fy are shy oa qh, Hep are’ k+t equivalent provided transition. e—— of 8(4,,0) ant 6%, ,0) ore in the Sahav k equivalance « Chrok out whether 6(%4)0) and §( 4,0) are dn the Some equivalence cles giv Mk for ew aes FE 805 Oy ond Ys are KH equivalent, — Tn yes Qt fs furtrer oleviced into te equivalance clames. Repeat thes fw exery oF in Me to get al te elments Je Meet:* Skebe32- Construct For for net, 2, %- =. UNeeL - Pen = Fonte > SSPE Construction of rtnibum autrreatums— for the > require wintinum ctelt autawalim » Fhe The stute table ts obtained replact ea Et, > the corresponding. equivalonce class [a]. Conetruct o. minimum gtote automatuns equiv de the finete autoratun closer?bod by figures State © , “4 % 4s Q, de Wy ® Yo a, Ya de, Ce ay ay ds ts ‘ta 6 oy VW ty 4a de& w Onp= Mel T= 11 { whi G0, 44 50 der daff MT IQL{ tedardey {Bry {te tef ma={ {topo {totah {teh of trots} ofte ef} ma={ {tape f{ trot} [9h {ooh} +f dan dsfh State o 1 ie Ves 45 BY) Bal Gas] ens [a, a4] [te] [a4] ‘ &) [\. a] Be] LAA [as 4s] [ay [as] = [ts] [tJ] etal wl = —_, =54. a; Le 4 qo te Ve, Ve 4 3 Ms Yo 4 as as Ls Ve, Vey Le ds Ge Vr Ve 43 r= fat f testi he, Ua te, Yeitrfh. m=] {as}ed a ag. hfe walfaty | mae [{astef to det fas} faset fart ro (Mah ete) Latch fasted ta}State o b =. a) Tart) —- E4ode] Ia, %s] Bet) [4.90] [Re ta] [4%] Lays [43] Tt] L410] [uy [to] Tu Tate] [42] [49 Tas] Tad mead "7" ARAHRAMA p @ a opera € WD ar HH ° 1 % a2 a uy “ts _ ts Ly . a, =e 4 ae fy ' : ! 2 moe [i deta}s{ tis Os dys ff ry Ef testa} d Gd 1ty aed UT IT3= { M= Ral Qe Gor Gay farts {arash {rat} 5 L se) Te Tas] fw] 143%) Tr.) Bal [sho] (ee as] Tray Bad Tay7Gmatruct o DPA equivalent to an NDEA whose Anantifin table sa olefiined sb w Stole 4, a Ge Aston tn StaBe 4 uy rS 4 @ 14 o Us oe fe 9243" de Ve VADNAIS }Gi) Qvatruct 0 minimum auteratuin DEA Stoty oO b tay Ut i Ye uy Vy 43 Ys 1a. ee i) ds 4 4, Ve ts 4s 4e Le 46 de % Vey 4% gol. D State ow b > [Ae] Ta. a2] [4048] [2 ‘7 [4a] Ga) [42] 12.7 it GE fat [a] yl [as] [As] : ray L ; J ) $ g % ) oWVVOCVEEUUTI YT ud LU Y bYdUEs oO ty > > > uwPi oy six fupte Moore Machine -°- A moore Machine a (@,2,4,8.4,4.) where WQ fs the pinite set op strates. GOS B the fnput alphaber . (if) 4 ts the output alphabet. iw) § is the transition function QxX¥ 3Q W) A tw the Output function mapping Qxa Wid Y, i the fnfttat state. Praesent stare Next state Output y aso a=i a Me Vs Us ‘a, ° “ Vv Ve 1 Vs W Ys é ws VW Ue o 8 Gisp° j Mey Meloy machines A melay machine has six | tuples (@ 3, 0,644.) where MQ iS the Finite set op states. @ = B&B the fnpur alphabet. (ia fs the purput alphabet. (15 is the transition func. @x¥ 9Q cere row iG %a e/ = = Ts the output gunction mapping QxS> 46 the jnitfal stote. a: Pxerent State Next State FV Prepreceer pe Covetston Meoly Machine to Moore Machine: ~ From preufous quustéen Ps. N's azo az olp UY i Qs : dae 4 Va ‘ oe ® ‘ vs Veo 1 Vs Veo VasMelay Machine = i. A relay machine # a gtx tuple (0,2,4.8,A0,4%) where Q ss tre fihrete set of states. = fs the snput alphabet A is the output alphabet & is the transition function from OX —> @ aA is te output funclion mapbing from = QxXEA q, ss th Sriltal tote « ~~ fresont state Nest fate azo | asi, State ole Stote o/e 4 4 | © 43, © Ge 4 L ty ° ds ts t ut t Ly Y | 4 ty 9 0» t oO 4, —— 1, v- O10 77] 2 v Yh ofp: ° L ° ditol t i ° t —— 12. >". ——> 4 ——> 4. ——>4, "4 ¥ 4 nt a 4 0 ° , , Op:- 00010 uw Conversion of Melee te Moore Machine Present State Next State Stott Op etude | OP wo | 0 > yy es ° ” L Q cache fom) | el qs 4) % 4 fe ty 2 q 4, Lot twye + Say nur ! 4, #4 ps eve NS vt any yee ~ No | q : * 9,790 3 Lo Geo / ay Guin)Ns WY ps of ofp 4 4, % Tao ° dyo a) A fat Qa 4s 43 machine nest page 441 4 TAHT 4 RePR APP PP PPP PORConstruct, a Moore Machine equivalent bo Melay mechine) ond defined ’y 7 © Machine od CPrévfous question) “PPAPAPARARAPMRAHHNNODOADRAOTRDAR >A a > ADP >eee enn Present StateYYUWVUUUEsuuaeee p.S N-S azo! az|\" sate} ole) Stare | ofp 4, Vex, zy) 4az, a hoe yz?) Garg) ze) Ha fe 4s 2g V2] 22] %z,] 2, 4. . Bz y Az, J AV} Az, | 2, Yaz 4 42, z a ‘| 42,1 2Mosre to Mélay Machine Z Construct a mackene while is equivatent be He moore machine defined by tee table