-92 Theory of Computation pete Treonyof Compan ERD Non Deterministic Finite Aut U ‘Definition of NFA veal The NFA can be formally defined as a CO! 1) Qisa finite set of states. 2) © isa finite set of inputs. 3) 8 is called next state or trans! 4) qo is initial state. 5) Fis a final state where FS Q Thus the ne: ition function. on of 5-tuples. xt question might be what is the ie i 1 states. ‘ e There can be multiple final s in theory of computations because they are mong of NFA. The NEA is basically used flexible and easier to use than th ‘AS. Example Fig. 1.10.1 Non deterministic finite automata Difference in NFA and DFA Sr. No. NFA 1 NFA stands for Non deterministic Finite Automata. 2 For every input symbol there can be H more than one state transition, 3. NFA can use empty string transition, Construction of NFA is si imple TECHNICAL PUBLICATIONS® __ Construction of DFA is di DFA stands for Deterministic Finite Automata For every input symbol there can be only one state transition, DFA can not use empty string transition. ood n up-thrust for knowledgespoons Formal Lenguage Theory and Finite Automata ems Based on NFA | Pe oi fn NFA wit states 1-5 and inp alphabet (a 6) has flowing ta mt | 4 Wa) qb) | 1S 13) ) 2 (3) {3} aw ) \ ow $ solution }) Transition diagram Fig. 1.10.2 ii) 8* (1, ab) = 1 or 3 5* (1, abaab) = 1 or 3 or 4 or 5 GEERERETED Give sion-delerministic finite automata to accept the following language over (0, 1)*, The set of all strings containing either 101 or 110 as a substring. Ser ore TECHNICAL PUBLICATIONS® - an up-thrust for knowledgeLanguage Theory and Finite Ay, ate 1-34 Formal Theory of Computation Solution : 04 ) Fig. 1.10.3 powerful than DEA ? Just ETT PES DFA. In fact NFA can be converted to be represented by both NFA and DFA, ver alphabet Y\=(0/1)". “ Pa ennan ria Gna TER Draw NFA for strings ending wil ae a ed ie NA wo Solution : The NFA is not DFA. Thus any regular language © more powerful than equivalent an Solution : Uma 1. Differentiate between NFA and DFA. 2, Define formally with example - Non deterministic finite automata. Epsilon- NFA _The e-transitions in NFA are given in order to move from one state to another without having any symbol from input set D. Desa SPPU : Dec.-13,18,19, Aug.-17, TECHNICAL PUBLICATIONS® - an up-thrust for knowledgeTheory of Computation ae Fig. 1.41.4 this NFA with e, qo is a start state with input 0. Initially with input 0, we can go to 40 or qu. Similarly with inpat 1, we can so to state 41 or qp. Thus it is not definite that on i is called moves to simply change the states, ‘put 1 whether we will be in state ; hat on inpu 41 or qp. Hence non- deterministic Finite Automata (NFA) and since there are some € it is called NEA with e. Definition The language L accepted by NFA with e, denoted by M =(Q, 5, 8, qo, F) can be defined as : : Leh M=(Q 5,8, q9,F)beaNFAwithe. f where ‘ Qis a finite set of states. E is input set. : Sis a transition or a mapping function for transitions from Qx {2UE} to 22. qo is a start state. F is a set of final states such that Fe Q. The string w in L accepted by NFA can be represented as L(M) = {ww € 5 * and 8 transition for w from qo reaches to F). | sas Si = Construct NFA with © which accepts a language consisting the strings of any mumber of a's followed by any number of b's. Followed by any number of c's. PPU : Dec.-19, End Sem, Marks 3 Solution; Here any number of a's or b's or c's means zero or more in number. That means there can be zero or more a's followed by zero or more b's followed by zero or more c's. Hence NFA with € can be - Fig. 1.14.2 TECHNICAL PUBLICATIONS® - an up-thrust for knowledgeFormal Langue Theory on py ' fone Tne OF py Mn My ‘4 Normally c's are not shown in the input atring. The transition table can be a ¢ We can parse the string aabbee as follows - 8 (qo, anbbee) 8(qo,abbec) F 8(ao-bbee) F 8 (qo,ebbec) 8(q1,bbec) + 8(q1, bec) F 8(q1,¢0) + 8(q 1.800) F 8 (42,¢0) F 8(q2,¢) F 8(q2,£) Thus we reach to accept state, after scanning the complete input string. GEEEEIEEETED Compare NFA and NFA-e. Solution : © The NFA and NFA€ both are non-deterministic in nature. * There are no ¢ (empty) transitions in NFA whereas there are empty transitions present in NFAc. * NFA occupies less space whereas NFA occupies more space. Thee - closure (p) is a set of all states which are reachable from state p on €-transitions such that : i) + closure (p) = p where pe Q. - Closure ii) If there exists ¢ - closure (p) = (q) and 8(q,2) = r then e - closure (p) = {4 " TECHNICAL PUBLICATIONS® - an up-thrust for knowledge — |tmeory of Computation 1-37 Formal Language Theory and Finite Automata er Find € = closure for the following NFA with ©. Fig. 1.11.3 solution : e-closure (qo) = e- closure (a1) obtained from q; with ¢ input. {40-41-42} means self state + € - reachable states. {41/42} means q; is a self state and q2 is a state ¢ - dosure (q2) = {a2} Review Questions Describe - NFA with null moves. Give the formal definitions of following with suitable examples ta. non-deterministic finite automata and deterministic finite automa Explain the extended transition function NFA with epsilon. US Ceo Epsilon closure, 3 NFA with ¢ to NFA without ¢ ESOS ECS RECN Steps for Conversion 1. Find out all the € transitions from each state from Q. That will be called as e- closure {q;} where qi € Q- > Then 8 transitions can be obtained. The 5’ transitions means an ¢-closure on 8 moves. Step -2 is repeated fo: Using the resultant state: be built. © each input symbol and for each state of given NFA. .s the transition table for equivalent NFA without ¢ can 8(qa) = € - closure(8(5(ae) , a)) where 8(q,e) = € - closure(q) TECHNICAL PUBLICATIONS® - an up-thrust for knowledgeThavy'a Cutan tea Foil Lngneye TH00ry aH Pity yy Mornay Convent the given NEA wit e 0 NEA without Fig. tad Solution ¢ Wo will tint obtain = closure of each tlate je, we will find out ¢ Teachaby, stats Crome cHETent state, Vener fe losure (ajo) = {dora dat bs losure (qn) = {aa} t= closure (q2) + {a2} Ase + dlosury (qo) means with null Input (no Input symbol) we can reach to qo , gor qge In a similar manner for qy and qa 0 + closures are obtained. Now we will obtaig §* transitions for each state on Sqo.d) +e closure (8(8(408)-0)) = ¢ = alosure (5(¢ -closure(qo), 0)) = e+ closure (8(qo/ 41-42), ) = c= closure (8(qo, US (q1,0)U 8(q2/0)) =e closure (qo U dU 4) » e= closure (a0) - {a0 qv qa} B(qo. 1) = e+ closure (8(6(a0."), 1) = c+ dlosure (8(qo/a1-42)> 1) = e+ closure (8(qo, I)U8 (qr, IU S(q2, 1) = © closure (QU q) U8) each input symbol, = v= closure (q1) GoD = {aa2} 8 (41,0) = © closure (86a Lt), °)) = © dosure (8(e - closure(q 1), 0)) © + elosure (8(q 1,42), 0) TECHNICAL PUBLICATIONS® « an up-thrust for knowledgereenyof Computation sav) 8’ (q2,0) 8 (q2/1) 5 (q2,1) 5 (q0,2) 4 1-39 Formal Language Theory and Finite Automata e = closure (8(41,0) 4 8(q2,0)) - closure (U4) e = closure (¢) ¢ € - closure (8(( 12), )) € - closure (8(€ - closure(q4), 1) e- closure (8(41,42),1) €- dosure (8(q1,1)U 8(q2, 2) & - dosure (q; U 4) € - closure (q1) {a1 a2} € - dosure (8(8(42.£),0)) & - dosure (8(¢ - closure (q2),0)) € - closure (8(q2,0)) € - closure (9) ® € - dosure (8(6(a2.), )) & - closure (8(€ - closure(q2), 1)) € - closure (5(q2,1)) € - closure ($) o e - losure (8(8(q0,e),2)) € - closure (8(€ -closure(qo),2)) & - closure (8(q9,41/42)/2) € - closure (8(q9,2)U8(q1/2)¥8(q2,2)) e - closure (U ¢Uq2) € - closure (q2) {a2} TECHNICAL PUBLICATIONS® - an up-thrust for knowledgeTheary of Computation 1-40 Formal Language Theory ang Finte Atom, §'(q1-2) = © - closure (8@(a1#).2)) * © closure (8(€ - closure (q1),2)) > © closure (8(qy,q3),2) = & = closure (5(q1,.2)08 (42/2) = €- closure (0U q2) = {92} - € ~ dosure (8(8 (q2.£)-2)) = &- dosure (8 (¢ - closure(q2), 2)) = © ~ dosure (5(q2,2)) = €- dosure (q2) = {a2} Now we will summarize all the computed 8’ transitions - 8°(a0-0) = {a0-41-42} 8°(a0-1) = {1-42} & (a0. (a1. =o, 841-1) = {41-42}, 5°(41,2) = {a2} °. 8°(42,2) = {a2} From this we can TECHNICAL PUBLICATIONS® - an up-thrust for knowledgePe a Computation 1-41 Formal Language Theory and Finite Automata The NFA will be as shown in Fig. 1.12.2, Fig. 1.12.2 Here qo, 41 and qa is a final state because ¢ - closure (qo), e- dosure (q;) and € - closure (q>) contains final state q2- nee Convert the following NFA with € to NFA without e. —O+O--6 © Fig. 4.12.3, ne Solution : We will first obtain € - closures of qq, q1 and qz as follows. €-dosure (qo) = {qo} &-dosure(q1) = {q1,q2} &-dosure(q2) = {q2} Now the 8” transitions on each input symbol is obtained as (40,4) = € - elosure(8(5(40,£),a)) = e-closure(8(e - closure(q),”)) = €-closure(S(qo,2)) = €-closure(q1) = {41/42} 8'(qo,b) = €-closure(8(8(a0.2),b)) € - closure (8(¢ - closure(qo),b)) TECHNICAL PUBLICATIONS® - an up-thrust for knowledgereory of Computation 5(aya) (art) ¥(q2,0) 5’ (a2,b) 0 4-42 Formal Language Theory ang Fito \ t 4 & - closure(8(qo-b)) 9 e-elosure(8(6(a1-£)-*)) & closure (5 (¢ - closure (4 1))) e -closure(5(q1, q2):") = elosure(8(q10)¥ 8(42/")) = closure($U ) é e- ctosure(6(6(a1-8)-b)) ¢- closure (8(¢ - closure(q1),b)) e-closure(5(q1, q2)/b) - closure(8(q1,b)U8(42/b)) €- closure(@U q2) € -closure( q2) {a2} e-closure(8 (5 (42.¢),4)) € - closure (8(¢ - closure(q),a)) - closure (8(q2,2)) € -closure(9) 4 € -elosure( 8 (8(q2,),b)) e - closure (6(¢ -closure(q2),b)) € - closure(3(q2,b)) € - closure( q) {a2} TECHNICAL PUBLICATIONS® - an up-thrust for knowledge| 3) For the state [ q1, q2---dn] € Q’ of DFA if any one state q, is a of NFA then [ 41, q2-----dn] becomes a final state. Thus the set ore Sete final states € F’ of DFA. all the SEETRALSD Convert the given NFA to DFA. ‘Theory of Computation 1-46 Formel Language Theory and Finis 0 1 {40.43} % | a | 93 $ Le® Solution : As we know, first we will compute 8’ function. 5({ao}. 0) = {40 aa} Hence 8’((qo],0) = [40-41] Similarly, 5({a0}-1) = {a0} Hence 8’((q0]-1) = [a0] Thus we have got a new state [q9,q1]- Let us check how it behaves on input 0 and 1. So, 5 (40-41]-0) = 8((40],0) v 841], 0) = {ao-ai}u {a2} = {40/41/42} Hence a new state is generated ie. [q0-41-42] Similarly, 8'((40-41]-1) = 6((40] 1) v 8((q1] 1) = {ao} {ai} = {qo-ai} No new state is generated here. TECHNICAL PUBLICATIONS® - an up-thrust for knowledge1-47 Formal Language Theory and Finite Automata ot! ercomputst” ction will be computed for [ao, ‘uf 41/42] , the new state being generated. again 8” Input ae wd ~ fosee] [es bd [soa] ‘As, you have observed in the above table for a new state [q9,41-42] the input 0 will ave a new state [0-41-4243] and input 1 will give a new state [40-41-43], because 51((a0-a1-42]-9) = 8'({40] 0) v8" ([ai] -0) v 8’ (La2] -9) = {ao-ai}u {a2} v {as} = {40-41-42-43} = [ao-a1-42-43] [aoa] [owed Derren] [tora] ovat bowel boon) | [rea 429] © [avaige-as] DFA for example 1.13.1 TECHNICAL PUBLICATIONS® - an up-thrust for knowledge| Formal Language Theory and Finns A Theory of Computation 1248 Construct DEA equivalent to tl Solution : The NFA M = ({p, q, r, sh, (0, 1), 8 (ph (s}) The equivalent DFA will be constructed. eo a Pee - or — @® a tl _Pal Ip, va [pr Pan bang ma al Bas} tpl fo a 0) TECHNICAL PUBLICATIONS® - an up-thrust for ‘knowledge4 1-40 _Fomial Language Thoory and Finite Automata Ipaq a) Ips 0} Ign a} It) Ip. q 8) [po] _@D man { spe ial state F’= {Ish [p 4% 8h tp, a sh (p, x, 8], (p, 8} } transition graph shows two disconnected parts, But part I will be accepted as sl FA because it consists of start state and final states, in part II there is no start sate. Fig. 1.13.4 GERRY convert tte given NFA fo DEA. Fig. 1.13.2 TECHNICAL PUBLICATIONS® - an uprthrust for knowiedge |= “heory of Computation 1-60 Formal Language Theory and Finity A \utom, a jolution : For the given transition diagram in problem statement we will firg cong eens ray State / = he transition table. 4% {a1 a2) {aah Now we will obtain 8’ transitions for each state. 8 (go) 0) = tao = laol 8 (gob 1) = fan) = fal 8 (il 9) = tara) = [q1/42] > new state generated. 8’ (qi 1) = fai) = fail 8° (q2), 0) = (a2) = [qa] 8’ (q2) 1) = ta1-a2) = [q1-42] Now we will obtain 5’ transitions on [q1,q2]- 8° (f41- 42), 0) = 5 (lai), ) v8 (a2), 0) = (aia) ¥ {qa} = (qr-a2) = [a1-42] 8° (fq, 42) 1) = 8 (fai) 1) U8 (laa), 1) = fail ¥ (a142) = [qi-qal TECHNICAL PUBLICATIONS® - an up-thrust for knowledge’ 1-61 poo compete ve [ayaa] #8 final state a8 well because it contains a final state qa. The the soe for the constructed DPA will be - Formal Language Theory and Finite Automata transition (@ lay 92) la.) [ay92) ‘an be eliminated Fig. 1.13.3 Consider a string 0010 we will get - Using NEA qo 0010 + 0490110 + 00g 9110 + 001q;10 + 0011q;0 + 00110q2 or + 001109; Accept non-accept. Using DFA 4000110 + 0490110 00g 9110 001q 110 Te Ts TECHNICAL PUBLICATIONS® - an up-thrust for knowiedgeoS Thooiy oF Computation roe Formal Langnnyn Theory agp Fy Ay ln, be OOH yO OOO yy dod Avoopt alate, Vw both the NEA and DEA aenept the janie stringy 0110 exam 1.13.4 ROMINA wn not containing 101 HA ontotriyy » fy aivepting all paxeible airingge of cenven anid ane not contain TOL Am a nuh, ay } bring Solution: The NEA reprenenting the alrliye that dot 1 The equivalent DEA will be L Be COLO Construct a NEA and then equivalent DEA accepting string over (0, 1), fr es not contain OL a a substring 10, 12, accepting all possible strings of zeroes anid ones which dl ci Solution : NFA will bo DFA will bo TECHNICAL PUBLICATIONS® « an up-thrust for knowledgey 1-63 oes aa Formal Language Theory and Finite Automata Convert given non-deterministic finite automata (NFA) to deterministic ee mate (DFA). Informally describe the language it accepts, i i EE ol 0 1 Pop dP ph Lucedale ® acc le I (casual cole laity golation * xp. 0) = IP q) > lp, ql new state xp. 1) > tp) = Ip] state 8.0) = ¢ &q) = {r) = [r) state ar, 0) = Ip, 1) =p, 1] new state &r, 1) = {q) = [aq] state Now, we will find input transitions on newly generated states. Alp, q) = IP al Sp.) = ip lp, 1 0) = {p,q 1) = Ip, q, 1] new state &(p, 1, 1) = {p,q} = [p, ql new state ap) = [pat Mpa 1) = [pa tl The transition table for NFA is - * eee. pat TECHNICAL PUBLICATIONS® - an up-thrust for knowledges 1-64 6-6 Formal Language Thoory ana fy Thoory of Computation Ae Fig. 1.13.4 into if it it DFA. Convert following NEA into its equivalen 5,0) - {P,Q }=[P, Q] New state Solution : 8,1) = 5(Q0) = 8(Q1) = 8(R,0) = &(R,1) 5(S,0) 8,1) = “ov or nw ww The 6 transitions can be applied on new state [P, Q] 5(P,Q).0) = {P, Q R}= IP, Q, RI New state 6(P,QL1) = R 5(P,QR],0) = {P,Q RK, S)=[P, Q, R, S] New state 5(P,QR),1) = {R, Q) = IR, QI New state TECHNICAL PUBLICATIONS® - an up-thrust for knowledgeyr i computa 1-85 ans * WARSI qn. oR) = {RQ S)=IR, Q S] New state (R00) * {RS} = IR, S] New state aq(hQ0 * RQ sh 5) © IR, SI gros) * RAS sqh-sh0) = S $(R-S)1) = [Q, S] New state s(.sh0 = IRS) 8(25)1) = IRS) Form 1a Language Theory and Finite Automata As no new state is getting generated we will stop applying 5 transiti sanction table for DFA is as follows. Er ieatsha enone _ Ra + ROS) Qs RS aoa Construct an — equivalent States/Z] 0 1 DFA for the following NFA : Tat y Cl CeO ® @| a] t = iu] TECHNICAL PUBLICATIONS® - an up-thrust for knowledge—™ ates Formal Language Theory aa rip ite 4, ti Theory of Computation Solutio ply § transitions on each state using eacl S(p.0) = Ip, q) = Ip, ql new state Sp.) = tq) Spal) = {p,q 1) = Ip, q, #1 new state SUpaht) = tq, 1) = Ig, 1] new state Sdpa.th0) = Ip qt) Sdpan0 = [qr] S(lq,1).0) = Ir] Sah) = Ur] iti As no new states are getting generated. There are no 6 transitions. The transition table will be =5 Ip bal Here r state can be eliminated Fig. 1.13.5 Let M= (lq9,4,), (0, 0, 8, qo, (9) be an NFA Where 5(40,0) = (99,41) 5(q0,1) = {q1) (40,0) =o 591.1) = (90,91) Construct an equionient DEA, TECHNICAL PUBLICATIONS® . an up-thrust for knowledge‘ormal Langunge Thoory and Finite Automata 1 ae anne 6 faction an follow: we gowtlo” B sao» Biaor sav = Moat ye tal ~¢ sav) * taooatl vat apply Siransition On (qq. gy) slate }.0) © [oa (aoa) sao siiqoan) © there are NO new alates getting generated, there is no application of 6 transition ence the transition table and transition diagram for equivalent DEA is lana] | (ay) {0.91 (40.91) | Loa) [BUI NFA with Epsilon to DFA Conversion subset Construction Mothod Algorithm step 1; Initialization step Let, ¢ - dosure (s) be the states in Dstates of DFA. Stop 2: Repeatation step ‘While (T aro tho unmarked states in Dstatos) mark T for (oach symbol a) { U = ¢- clopure (movo (T, a)) Af (U fo not in Detates) Add U as unmarked state in Detates Dtran [T, a] = U } // ond of for }// ond of whilo, TECHNICAL, PUBLICATIONS® - an up-thiust for KnowledgeThey Oovnputation 10 Pomel Lananage Thacry art Finig hot om, Cin Comert the follwing NEA with © to equivalent DEA t Fig 1.444 Solution : To convert this NPA we will first find eclosures, C- closures {qo} . {40/41/42} f-dosures {41} = {41,42} C-closures {42} = {qo} Let us start from e-closure of start state €-dosure {49} = {qo/q1rqz} we will call this state as A, Now let us find transitions on A with every input symbol, 8'(A, a) = € - closure (8(A,a)) € - closure (8(qo,q4,q2),a) © -dlosure {5(qo,A) U B(q4,0) U 8(q2,0)} = € -closure {q;} {41/42}. Let us call it as state B, 3A, b) = © - closure (5(A,b)) € - closure (8 (qq, q1, q2),b) & = dlosure {6(qo,b) U 8(q1,b) U 8(qp,b)} = e closure {qo} = {4o, di-qa}ie. A. Hence we can state that 5(A, a) = B 8(A,b) = A Now let us find transitions for state B = {4,4} 8B, a) = €- closure (8(q4, q),2) TECHNICAL PUBLICATIONS® - an up-thrust for knowlodgoYe anutanyy Former Language th bs Language Thesey ane Finite Automaty mace of Se » (aveae} be 8 BIR W & & = elostire (CQ), qy).b) =e = clostite {8(q4,b) U 8(qy,b)} = + closure {qo} » {Qo Mega}ie A penwe the generated DFA | Fig. 1.14.2 en Convert the given NFA into its equivalent DFA - Fig. 1.14.3 Solution : Let us obtain € - closure of each state. e-dosure (qo) = {40-4142} e-dosure (qx) = {41-42} e-dosure (q2) = {42} Now we will obtain 8’ transition. Let € - closure (qo) = {qo, 41, 42} calll it as state A. 8(A,0) = €- closure {5((q0,41/42)-0)} = €- dosure {8(q0,0) UV 5(q1,0) V 5(q2,0)} = €- closure {qo} = {40/41/42} ie. state A TECHNICAL PUBLICATIONS® - an up-thrust for knowledgeTheory of Computation 1-00 Fora! Languago Theory ond ny j See 2 Au SCA) & = closure {8 (qo, 41/42)/1)} > c= closure {5(qo,1) U 8(q1.1) U 6(q3,1)} = e+ closure {qi} = {q1-4q2} Call it as state B S(A,2) = €- closure {8 (qo, 41,42), 2)} &- dlosure {8(q9,2) V 5(q1,2) U 5(q9,2)} = €- closure {q2} = {q2} Call it as state C, Thus we have obtained 3A = A sa) = B 5A.) = C (y @- 2 Fig. 1.14.4 Now we will find transitions on states B and C for each input. Hence 8B, 0) = e- closure {8(q1,q2),0} €- closure {8(q1,0) U 5(q2,0)} = €- closure {9} =o 8'B,1) = €- closure {8(q1,q2),1} = €- closure {8(q1,1) U 8(qp,1)} 1 = © closure {q1 } TECHNICAL PUBLICATIONS® - an upthrust for knowledge= {41-42} te state B ftsett, 81,2 + # > omure {6(q5,43).2} + 0 domre ( 8(q4, 20 Mqy.3) © #- demare {q,) ~ (90) ie mate © Hence baH- 6 sm B BH C The partial transition Aingram wel te $8 he tas Now we will cite trarvitions tor C BCD = € > chomave { Hq, Ob} « ©» domare (#) * 8X1) + €- dome (Biqy.)) = €- camase {@} BID ~ €- cdosure {8(q2.2} TEQHNICAL PUBLICATIONS® « 4 up-twuat for hnomtengeFormal Largyoge Tt 2 itty _—— "heavy of Computation Venee the DPA fa Fig. 1.14.6 h final state qy lies hence A is final state in B = , {419.3 final state in C = {q2}, the state q, lies hence ¢ jg “#2 i qa} in whic As A= {qo,a1/42} (ny the state qp lies hence B is also final state. Convert the given NFA with e to its equivalent DFA. Fig. 1.14.7 Solution : e - closure {qo} = {40/41/92} e - closure {qi} = {a1} e - closure {qo} = {q2} e- closure {q3} = {q3} e- closure {qu} = {aa} Now, Let € - closure { qo} = {40/41/42} be state A. Hence 8’(A,0) = e - closure {8((q0/41,42),0)} = €- closure {8(qo,0)V 8(q1,0)U 8(42,0) } = €- closure {q3 } = {qg } call it as state B. TECHNICAL PUBLICATIONS® - an up-thrust for knowledge. of Computation Theor of Computation tons ‘ HHH L mgionign PRany ane Piha Anitantintt BIA) = + elomute (Btigo,qy.ayhth} =e Closure {B(a6. 1) (41) Bay A} + F< dome {qs } Sqn. the partial DEA will be Fig. 1.14.8 Now, B,0) = €- closure {8(q3,0)} 6 8,1) = €- dosure {5(q3,1)} = © closure {q3 } = {qs} ie. statec 5(C,0) = &- dosure {8(q4,0)} = 9 8G) = €- dosure {5(q4,1)} ae The DFA will be, Fig. 1.14.9 Convert the given NFA~ A to an NFA, : TECHNICAL PUBLICATIONS® - an up-thrust for knowledgeFormal Lenguaga Th, 1-64 8OrY and “nit Theory of Computation 0 Ay, 0 Fig, 1.14.10 Solution : We will e-closures of A, B, C, D and E. e-closure (A) = (A, B, D} e-closure (B) = {B} e-closure (C) = {C} e-closure (D) = (D} e-closure (E) = {E} The 8’ transitions on each input symbol is - 8°(A,0) = e-closure (§ (-closure (A), 0)) = e-closure (6 ((A, B,D), 0)) = e-closure (A, C, E) = e-closure (A) e-closure (C)Ue-closure (E) {A, B, Du {C}u (E} {A, B, C, D, E} e-closure (5 (-closure (A), 1)) 1 8 (A,0) 8’ (A,1) u e-closure (8 ((A, B, D), 1)) e-closure ((E)) 8° (A,1) = {B} 3’ (B,0) = e-closure (6 (¢-closure (B), 0)) = €-closure (5 (B, 0) = e-closure (C) 3’ (B,0) = {C} 8’ (B,1) = (E} TECHNICAL PUBLICATIONS® + an up-thnust for knowledgeTreen of Compuation 1:65 Formal Language Theory and Finite Automata S'(C,0) © e-elosure (8 (e-closure (C), 0)) e-closure (8 (C, 0)) G0) = 6 8G) = e-closure (8 (¢-closure (C), 1)) = e-closure (8 (C, 1)) = e-closure (B) 8'(G1) = {B) 8’ (D,0) = e-closure (6 (¢-closure (D), 0)) = e-closure (5 (D, 0)) = e-closure (E) = {E) 8’ (D,1) = eclosure (6 (¢-closure (D), 1)) = e-closure (8 (D, 1)) = e-closure (9) 8,1) = 6 8’ (E,0) = e-closure (6 (E, 0)) = e-losure (@) 8 E0) = 6 Similarly, 8’ (E,1) = 9 ‘The NFA can be represented by following transition table. TECHNICAL PUBLICATIONS® - an up-thrust for knowledgeTheory of Computation EESEY Minimization of DFAS Formal Language Theory gy a ety The minimization of FSM means reducing the number of States from While minimizing FSM we first find out which two states are Tepresent those two states by one representative state, Biven p “Wivaleng im ‘ e tay Definition of equivalent states - The two states q1 and qp are equival 8(qq,) and 8(q2,X) are final states or both of them are non fi X€E*(2" indicate any string of any length) we can minimize the Biven pot finding equivalent states. Fs ent ji Mal states ay by Method for Construction of Minimum State Automata : Step 1: We will create a set my as -{ QQ } where Q? is set ofall fing Stay and Q) = Q-Q? where Q is a set of all the states in DFA. ts Step 2: Now we will construct mx, from mx. Let QF be any subset in x, . 2 are in QE they are (K+ 1) equivalent provided 5(q1,a) and 8(g a ang equivalent. Find out whether 8(q3,a) and 8(qa,a) are’ residing 42? . equivalence class mx. Then it is said that qy and qp are (K + 1) equiyae Thus from QK we create (K + 1) equivalence classes. Repeat Qfin my and obtain all the elements of Rey Step 3 : Construct x, for n = 1, 2, Step 2 for every until ty = tae. } Step 4 : Then replace all the equivalent states in one e state. This helps in minimizing the given DFA. Let us understand this method with the help of some examples. Gar Construct the minimum state automaton for the following transition diagram, quivalence class by representative Fig, 1.15.4 TECHNICAL PUBLICATIONS® - an up-thrust for knowledge. ‘Theory of Com utation re tO Fomnl Language Thaory and Finite Automata classes, We will start constricting equivatonce Input Step 1: We will first find 0 - equivalence. For that purpose we will create two sets - one set containing all the final states and other set containing all the non-final states. 0 - Equivalent = {q9/q1/42/94/45/46-47) (43) Now will check equivalence among all the states of {qo, 41/42/44 45/46, 47} by means of mapping functions (qo.a) = 8(qo,b) 3(q1-a) = 8(q1,b) = i T Belong to same set Belong to same set ‘qo and qj are equivalent. In this way we will consider every pair from the set {0,41 92" 44 45 46-97) Now consider pair {q9,q2) 5(qo,a) = ¢_ Belongs to different sets 8(q2,a) = qo and qz are not equivalent Step 2 : Now will find 2 - equivalence from the sets obtained in 1 - equivalence. TECHNICAL PUBLICATIONS® - an up-thrust for knowledgenee 6 ayy 68 ae eaten Trees oF CoeURANO _ We will compare qo with gy, g a ‘ty, qo! firs Consider the set {gor dry 45 46 4 find 5(qo.b) = Sqoa) "/1 8(q1,b) = le ‘ Sara) =\ao, Belong to different sets Belong to same set e set. “Qo and qy now does not belong to sam Now campare states qq, q5 states. 8(qo,a) = a1 S(qs.a) = 46 i id. “+ Gor 4s are not equivalent. Now we will compare q; and qs 5(q1,b) = (qa) = a a 8(q5,a) = (qs, T Belong to same set Belong to same set That means - qj and qs are equivalent. Hence the 2 - equivalence set can be Write, as - OO 2 - equivalence = (qo, 46}, {41,45}, {42-44}, {43}, (a7) Step 3 : We will compare {q0/ 46) 8(qo,a) =, 8(qo,b) 5(q6,a) =' 5(q6,b) Tt Belong to same set Belong to same set * (Wo, 46} are equivalent. Similarly, we will compare {q1,q5) , them as equivalent. Hence 3 - equivalence set is as follows - a 3 - equivalence = (qo, q6}, {q1-95), (92/94), (93), {a7} {92-44} and we find As 2 - equivalence and 3 - equivalence are same sets. We will stop finding further equivalences. Hence we can have minimized transition table and minimized DFA as follows - TECHNICAL PUBLICATIONS® « an up-tnuat or knowledgereoryof Comput 100 Formal Language Tinory and Platte Automata Input “ b Stato ~ , Mor gal tent taal Vay ael lor dal tavad laa taal tay ail : taal hl ao dl lal odd as ‘The transition diagram with minimized states is - Fig. 4.15.2 Part III; FA with Output ed The finite automata is a collection of (Q, 5, 8, qo, F) where Q is a set of states including qo as a start state. In FA after reading the input string if we get final state then the string is said to be "acceptable". If we do not get final state then it is said that string is "rejected". That means there is no need of output for the finite Automata. The ‘accept’ or ‘reject’ acts like ‘yes’ or ‘no' output for the machine. But if there is a need for specifying the output other than yes or no, then in such a case we require finite automata along with output. There are two types of FA with output and those are : 1) Moore machine 2) Mealy machine TECHNICAL PUBLICATIONS® - an up-thrust for knowledge170 Pete LACHO® TNOOFY Uk! iy Prmeyy n Coapettih te, : ine in which the next state is deciceg 1 symbol ata given time depends oh te 1 of Moore machine is, 'y oy ‘Moore machine Moore machine State and current input eymbol. The ; Present etate of the machine, The formal jx h finite state machi outpul definition . where Moore machine te a six tuple (Q, £8, 8. 4 do) OQ is finite set of states. 2 is finite wet of input symbols. a is an output alphabet. 5 isan webs ein ach that Qx¥ > Q This is also known as state function. is output function Q— A. This function is also known as machine function. Qo _is the initial state of machine. For example Fig. 1.16.1 Consider the Moore machine given below - The transition table will be - TECHNICAL PUBLICATIONS® . an upthrust for knowledgetation Q Freoy of oe Se 1:74 2 Formal Language Thoory and Finite Automata In Moore machine output is associated with every alate, In the above given Moore machine when machine is in qo state the output will be 1, For the Moore machine if the Jength of input string is n then output string has length n+ 1. For the string 0110 then the output will be 11110, Mealy machine Mealy machine is a machine in which output symbol depends upon the present input gymbol and present state of the machine, The Mealy machine can be defined as - Mealy machine is a six tuple (Q, 3, A, 8, A, qo) where is finite set of states, is finite set of input symbols, Q z A is an output alphabet. 8 is state transition function such that QxE>Q. a is machine function such that QxE—> A. qo _is initial state of machine. For example, Fig. 1.16.2 For the input string 1001 the output will be 0001. In mealy machine the length of input string is equal to length of output string. Difference between Moore and Mealy Machine 1) Length of Moore machine is one longer than Mealy machine for given input. 2) Secondly output of the input will be along the edges in case of Mealy machine but it should be associated with the state in case of Moore machine. TECHNICAL PUBLICATIONS® - an up-thust for knowledge4-72 = Tilley Theory of Comput? = odin Mach re and Moly rate 1 complement of given bing TY ny ree None Problems Based on Moo or sent CEENATAD ves re cine Spr Solution : * Logic To generate 1's compleme apply is that if input is 0 then outpt That means there are three state one and produces output as 1. Then thir output as 0. * Design in Fig. 1.16.3. Hence the Moore machine will be as shown 18 Fig. ry number the simple logic which wut will be 1 and if input is 1 ben output will wi estat state, second state is for taking gy tate is for taking 1's as input ang Proayat 8 nt of given bina Fig. 1.16.3 * Simulation For instance, take one binary number 1011 then | Input 1 1 0 0 Thus we get 00100 as 1's complement of 1011, we can neglect 5 a 7 : = eth the initial 0 and the output which we state ae] Output get is 0100 which is 1's complement of —f a [a [a | o 1011. The transition table can be ie ee ee drawn as below - Glow [oes 8 TECHNICAL PUBLICATIONS® - an up-thrust for knowledge, sreory of Compusaton 179 Formal Language Thoory and Finite Automata » machine M © (Q, %, Thus Moore mac (Q.%, A, 8, d, qo); where @ = fan, qq, ¢ £2{01 vq) (to. di aa}, 22 {01} re transition table shows the 8 and 2 functions, Deni Denign a Moore and Mealy machine for a binary input sequence stich that if i has a substrinny es the machine outputs A if input has substring 110 it outputs B otherwise HL outputs C, Cu CATAL golution ¢ + Logle For designing such a machine we need to take care of two conditions and those are checking 101 and checking 110, If we get 101 the output will be A. If we recognize 110 the output will be B. For other strings the output will be C. We can make a partial design of it as follows, « Dosign Fig. 1.16.4 Now we will insert the possibilities of 1's and 0's for each state. Then the Moore machine becomes. Fig. 1.16.5 TECHNICAL PUBLICATIONS® - an up-thrust for knowledgea Formal Language The, SUS Fia a Theory of Computation Now the Mealy machine can Fig. 1.16.6 i ‘ iven binary yp is shine to find 2's complement of a given ry nu GERORRLED Design a Mealy machine to fit ee eee Solution : * Logic For designing 2's complement of a binary number we assume that LSB to MSB. We will keep the binary number as it is until we read as it is then change remaining 1's by 0's and 0's by 1's. For example, input is read froy first 1. Keep that Let the binary number be 1011 = read from LSB Keep the first 1 from LSB as it is and toggle the remainin g bits we will get 0101 Thus 2's complement of 1011 is 0101. The required Mealy machine will be - * Design Fig. 1.16.7 TECHNICAL PUBLICATIONS . an up-tnuat for knowiedge“eon of computation $376 Formal Language Thaory and Finite Automata Denign a Moore machine which will increment the given binary number by 1. ttn! + Logle We will read the binary mumber form LSB one bit at a time, We will replace each 1 py dunt we pet fst 0. Once we get ft 0 we will replace Ht by 1 and then keep remaining DIES a8 it is, menor example + 1 0 1-1 & Read from 188 bit by bit » 9 1 0 r 1 0 0 0 T 1 1 0 «0 + 1 0 0 1 Using this logic we can built a mealy machine + Design Fig. 1.16.8 Give Moore and Mealy machine for &={0, 1, 2}, print the residue modulo 5 of input treated as a ternary number. Solution : + Logic The ternary number is made up of 0,1 and 2. The interpretation of teary number n can be - i) If we write 0 after n then number becomes 3n. ii) If we write 1 after n then number becomes 3n + 1. iii) If we write 2 after n then number becomes 3n + 2. TECHNICAL PUBLICATIONS® - an up-thrust for knowledgeTray oF Computation _ Por example, “Ny Ten © 4 then its value is 4x3° =4, Wwe write 0 after 4 ie. 40 = 4x3140x30 = 12 If we write 1 after 4 then hg i AL = 4x3l41x30 = 13 If we write 2 after 4 we get be, any, 42 = 4x3l42x39 = 14 For residue modulo 5 we will get remainder 0, remainder 1, 3 and remainder 4 values. Then we assume various states for the ie, * Temainder 9 * ese remainder,” qo ~ remainder 0 state s+ 41 - remainder 1 state 2 43 - remainder 3 state remainder 2 state 4 - remainder 4 state Now consider n = 4, For 40 we get decimal value 12 that means 12% 5 = 2 it gives remainder 9 For 41 we get decimal value 13 that means 13 % 5 = 3 it gives remainder et Similarly 4.2 given remainder 4, n= 4 itself is remainder 4, Hence we can design, —Y)—-@ ) Fig. 1.16.9 * Design Considering all possible cases we can design Moore machine as, TECHNICAL PUBLICATIONS® . an Up-thrust for knowledgeFig. 1.16.10 similarly the Mealy machine can be - 214 Fig. 1.16.14 TECHNICAL PUBLICATIONS® = an up-thrust for knowledge$$ 1-78 Fone Langvge Theor end Fag Theory of Computation a il read sequences made Up of eter ine that wi ign a Moore machine i ; Gana Desens wt the same sequences except that in case where gy 7 dna, O, U and will give as outps ine for the same ign the Mealy machin lows an E, it will be changed to U. Design ss i Ly, Solution : * Logic We will assume a separate state for each alphabet. The output of that State win ke corresponding letter. For instance / For alphabet A the state will be qp and output of dy ww be “ For alphabet te state will be q; and output of q, will be E. Continuing in fas] on we will have dy 42, 43 and q, states. The start state will be qy we will take care of one thing ang that is when I comes immediately after E it will lead to the state qy because output of state 4s is u. With this logic the corresponding Moore machine will be - * Design Fig. 1.16.12 TECHNICAL PUBLICATIONS® . an “p-thrust for knowtedge‘Computation ‘ Th nO onal Language Thoory andl Finite Audra Now we will draw the Mealy machine for the mame problem ju 010. UN WW Fig. 1.10.13 Here the Mealy machine has the output slong the edge self we have got only to state. The transition changes from qq to q; when we get E, ‘The I which is immediately following E will have the output U, Consider the string AIFOAEI will be give an output * AIEOAEU. 1% EL wi give an outpy Construct a Moore machine to determine residue mod 3 for binary number. Solution : « Logic This Moore machine is also called remainder 3 tester. In this machine we will get remainder 0, remainder 1 and remainder 2. To interpret the given binary number in its decimal value we consider n as a number if 0 is written after n then its value becomes gn. If 1 is written after n then it's value becomes 2n + 1. For instance, if n = 0 then its decimal value is 0 then, O1 = In+1=1x041-1 O11 = 2n+1=(1x2)41=3 Consider n = 1 its decimal value is 1. After 1 if 0 comes then its value will be 10 = m=2x1=2 If 1 comes after 10 then its value becomes, 101 = In+1=(2x2)+1=5 + Design With this logic we can construct a Moore machine with 3 states. qo is the start state and is considered as remainder 0 state. q; is considered to be remainder 1 state and q, is considered as remainder 2 state. Fig. 1.16.14 TECHNICAL PUBLICATIONS® - an up-thrust for knowledge80 Formal Language Than, Computation Theory Defi Mealy machi Construct a Mealy machine in quran) ine lv : : ‘ t is ever EVEN/ODD if the total number of 1’s in the input is even or odd. Th, fe =Oand 1. Solution : «= Logic ‘The restriction is on number of V's, There is no restriction on numpe. Mealy machine will then be - au \ + Design yODD con svopD & o A/EVEN Give Mealy machine for the following processes “For input from (Gi otherwise output z=, # input ends in 101, output X; if input ends in 110, output Y, ney ee Esa Le Solution : Fig. 1.16.15 Mealy machine TECHNICAL PUBLICATIONS® - ‘€n up-thrust for knowledgea Fig. 1.16.16 Moore machine 0 Construct @ Moore machine equivalent to the Melay machine M defined in following table with input alphabet, Ce TECHNICAL PUBLICATIONS® - an up-thrust for knowledge™ Treo of Conuitnton 1.62 Formal Language {wery oft We Auternaty Prom this machine we can observe that the edges leading to qy and qy state have the output 1 But the state gy has sutput 0 and 1. Similarly ealges leading to state q> have output 0 and 1. Hence we will split gq. as q) and Qh. Similarly we will split Gs a8 gy and qh. The Moore machine is as follows Design @ Moore machine for computing the 2's complement of binary number, Convert it into its equivalent Mealy machine. Solution : * Logic Applied : For designing 2's complement of a binary number, we assume that input is read from LSB to MSB. We will keep the binary number as it is unt] we read first 1. Keep that 1 as it is and then change remaining 1's by O's and o's by T's. © Example : Let the binary number be 1011 e Read from LSB keep first 1 as it is and then toggle the bits. Hence we get 0101 < This 2's complemented number. The Moore machine will be - Fig. 1.16.17 « Equivalent Mealy machine - Refer ex. 1.16.3. TECHNICAL PUBLICATIONS® - an up-thrust for knowledge