dnb? aa Introduction of Theory of Computation Automata theory (also known as Theory of Computation) is a theoretical branch of Computer Science and Mathematics, which mainly deals with the logic of computation with respect to simple machines, referred to as automata, Automata enable the scientists to understand how machines compute the functions and solve problems. The main motivation behind developing Automata Theory was to develop methods to describe and analyze the dynamic behavior of discrete systems. The theories of computability and complexity are closely related. In com- plexity theory, the abjective is to classify problems as easy ones and hard ones, whereas in computability theory the classification of problems is by those that are solvable and those that are not. Computability theory introduces several of the concepts used in complexity theory. Automata theory deals with the definitions and properties of mathematical mod- els of computation. ‘These models play a role in several applied areas of computer science. One model, called the finite automaton, is used in text processing, com- pilers, and hardware design. Another model, called the context-free granmmar, is used in programming languages and artificial intelligence Automata theory is an excellent place to begin the study of the theory of computation. The theories of computability and complexity require a precise definition of a computer. Automata theory allows practice with formal definitions of computation as it introduces concepts relevant to other nontheoretical areas of computer science,oO Nurnber, of, ones is even fe 4t . GeO Ze fot}sha trem autowk wow sof ack. Ay Attomaten WL aw ebstact Sy Pro pelad Cornpubing. clawica, whith Follnas a predolyrminod Sequante of. aperations automa / > AM purtomaken with a diwity mambtr— of Jrahs ‘is Calla 4 Pike Putomtton (FA) A Ft stele Machine ( FSM) Redolad Terminal sgies : 5 mpwilet - tn allphaber is any peas sot 4 Symbols. &- [E = {4,b,Gd4 is an abphabed sot hou a,b,c and A atu Symbol. © Sting - A string Bo gjvita stqumee dp Symbobs talon fom Z. Ex. \ capcada’ fs a vabidl staing on. the alphabet Set Fe J 4,664} > length dp a String 1S She swombte of Symnbsbs preset ah a Sting - ( Senvted by ISI). be ip [s=*cabeadal \sl=E S| Is|= 0 ,it fs cabled an empty Shing. ( Benokd ay 6):Muah d, Si Dh K (e3)) Lt = be an abpraket and Z=[a,b} Hon alld stings oy Lngih kCkz1) & denoted by =k, ° Ek= Cwiwha Shing d. Lmgth kK R21f Ex: O 2= 4% bp tho gle $4, 65 Ze faa, ab, ba, bb} P= fang, aab, aba, abb, bat, bab, pba, bbbt : lele2 = 2! C nog stings 4 Lang ona) \el= ye 2° jel= 8- 2° ® sz ¢0,1,23 S*= 4 00,01, 02, Ny 10, 12422, 20, 21f \Sl= 9-3” Contolmabion J. Shirgs « yw) amd ws osu two Stings tun contote nation fp Wa. ee ee Shing and At Us demoted by Ww) W,* Prapix de a Strings A stg obtained by romoving Lesip DL oko draiting, Axyrnbols 1S Callad pretix Ex: we abe —_ tha pefied, W= 4, ab, beSoRKK of a Shang ; ® A dping obtained by Aamoving Te) ol Mou backing | Aymiots Is called Saptir. ex Ls abl , hon Saphx os wW= C, bl, abcd Substsings 44 ea : A Boing Dbtainad by Abmoving g pry and Subbx pom Atsing wi Calbod Aulshiry a, Ww: &x: we abc , thn biha ae oy WD" Subst I; W= w- (me preyx) — (one Subtix) > Fora sping w, the Sting x fs a subshing of w, 1 tha sbing @Ppears ° hang nego : conbiguiously Ju W- > A lamguage L over S18 a Subse f e* ve iu a Colactim cy Strings over dhe alphabet ZS, > & a fe} ow languages > The language @ Vs Undohined as Aivnilasx to inprntty amd SEF VS Similan XO am empty box Le a Lamguage with ook amy arg Ly = $01, voll, ooo} 18.4 lawanege over {0.17 th = $ €, 0, 00000--~-f 15.0 laguage over Lo} tas $672 . m2iz a language TER language. is a sod 4 Sting all Chosen om some = bE ib an alphabet, and LCE® tm Lis «language ovens© KWerustar + The Klee star Z* |’ a unary pporuatol_ an a 48h oh Agios ok Abrngs, = , Wot gives tho Inpivth seb + ald possible Shing cf add powBible lng over F indbading A+ Se*=S0E,0BU------ WME Zp ia Daa Set ald possible abrivgs dr Lope P f&& g=$4,} aa da, baa, ab, ba bby = =~ of Rome Chodwre} POLS ¢ Tho Gh St % dhe Inprite Set 4, alt powstb2 Abings ad possible Langths Ok & exehusling A. + - = ©, VE, VS,0--7- 7° ets s*-fa} KLoone Cd pdusea dg 0 lomgunge ¢ Wk L be a ves Soma alphabet Z. Thon klenc Chosvee a L Is Annoted by L*® ona re 1 alo knowre Os Aabbaxive beovarbve (Dost and dapinod at dobbs « Le = 5 seh % al) wads over SF = PvUvtvD.- =ex. xX OSs {4,3 and a language ek nore @ LE Sats ene we U= {6} U = § 4,63 re § 4a, ab, ba, bb} and $0 %m- ) ae E,4,b,0a,%) ba, bb,-----3 © S= 403 » hrm SS: £,d, 06,000,0000, ~~ ~~ F Mapemalical Tnduchion imt)s Based on gennok obsess Vanons Speagic truths Can be (aonkied by puasoring' This prinupl % ae ynatamab’cad Induction, The prsot by MI Ynvolvte four Steps. Basic, Tris is to stasching pont Fob Including » Has prove, erat tro pasubk is due pel dome neo 4 apndurtion ,axsums ynat tro Arsubl y's Pus nok Wy pothesis * eee oo cmauifto sep 1 Prove Yaak tha AMUIKIB GRRE BS dors m=-Xt\ Prov, phindnckon step frcku od Powe,» me Powe tho pol. Sey by mi. Cee ml) a= Sobukign: Basis bi ni 4 , i Ae cEeluction Hypothisis 5 Tha weaubt js bus dot ns ke 42434 --4kK5 KURA] anduchen SIPS we have tv Prove Prat Hua yasuld . pug tre w= kt+H WiC ies aa oti ee SAS (eH GHD)face}, of Touction Spt LHS) = JF2tBE---- +K EK) = k RH) KH) jaa) = Ce) Cer =R-HS- Crrsemnans + A qBarnmas Jot Ergiish hanguage tells vs whether posdicudar Aentenco is welt fetmed A mot. A gave Gy fs clefined as a quadruple, G@= CV,7,S, PD whow yy — finite set 4, ote 7 — Yat set 4 obyects called Hrminal Syvbels. SEV is 2 Speciad symbul Called He stasd vaslablt, p is a Arb set ay productions > Ww pedluctin gules aso Ye huotd fa Qhammmas, they cperidy hao Ho qramenar branifedms cro Sting anto avethin, ond Hrcugh- this Hoy cing a language amouaied with Ho eammar. A predudio Aves ara oy he form > —7q, wohsu 1 1s an ehemont of CV UT)t ana y is in (vv1* a> Thee pwdadions wu applitel fn Hu gellesivg manner’ giver a sting w dy tho foo w= UXw > we Say te productln 24 fs ppb cable to the Abing, and we may vse Lt do Seplace % with Y, Here by obtaining a mo sring CaO a eee Z) Us Callas) Variables, >ee A) ee Grammar , hon tw Sep @ K(b)= f we te ss Soh is the lang gevoraled by G de ~ Sf WE L (Oy , Hon tee Sequente Gop wy = D-- -- Von Dw fs a dovvation oy Mo Sevtence w- Te Shings S$, Wi, Wa,---- Wn Which Contains vesdablg as well as terminals, aw Callach Sevtentiad forms of tha, Ativan ex: Consics the grammars Gi= ({83,14.%3, 6p) with P given by S7> aSb S>r Thane | S$ > asba aasbb = arbb So we Can weal SS aabb > The Sting aabb Ws a Bentento in the language genweattad by Gr wornia aaShb is a Senterttiad fore ‘ | ma 2 aterm. that gerenates Le Sane: nzo} Ex 1S — Ab tat (1583, Lad, SP) With productions S—>Ab A> 4Ab AZ AFinda Automate (Fay K jinicke cadomate Consists dp a vith number 4p States A FA Cow be Arpruserded by 5- tuple (R, = 8 Ww, F) who Q— pr memempty Set States = dmb monempiy set of inputs Cbled Inpat al prabe}- & - 2 function which ynaps Q XZ into Q and is vsuall Caled Avad bansition func Theis lb the function whidk cusonber tHe change dp Stes clsdng athe homsition: This mapping is ustrally Puprsrented by 4 pansition table ol pemasition clagtew Ww EQ jo Be initial state ecg is the Sebo nat stelle uo ee LA CITA spt te —> Reading htael Five Conte! Block Alagsam a_Finthe Atomats ; one tp pe ng The 7 ut is clivded ' Sqass was Conta ~ a ang vata Bom tho input alphabet 2 The end aquace dy whe *ape Conkafn end-mark ¢ or the Wt end and fat fra sagt gra. Atscone f Chenin jyelicates that the tape is A imprints Lewy: The Ugh te right Sequonce op Aypmests bedweene The end-maakons 1 Be pur Shing to—> Tre input to Ho dint Grho) will be vavally ; Synb, Une the R heod. aa Thank ition System ; A bantition ger Aa bravtttion System. laa devate dude labelled gape an which ead vetex(or nocle) Aoprosents a Stale and the Abaced eclges mdltate the pamiten fa Stake and to elges ase Labellad With Input) outpyy , Actoptabily ds a Shing by a PA: K Shing % {5 actapied bya FA M=(R,2,5,t0,6) ip Bl, d= 4 for Some TEP. Thic ig basically tte acteptability of a Shing by tw pmal Steal (fecep ng ey Ex Considas FA whose hemsition jn 8 Is given ‘in table « Hau 221 Udo}, Z= (Ob, F= ly. Give Be enloe pr ae a States fet the Input story AAopot. Inputs, States aaawie Alas 1 oes a 9) Y, Vo 4 = 43 dM. : 4s, a) Ve St §(4, Nolo) = d(%, Veler) J 8( Yo, 0/01) wv oS (4, 18D w 5( 42,20 8 (411) = El4, = %