Popular in Course
Popular in Computer Information Technology
verified elite notetaker
This 60 page Class Notes was uploaded by Kathleen Cartwright on Monday September 28, 2015. The Class Notes belongs to CIS511 at University of Pennsylvania taught by J.Gallier in Fall. Since its upload, it has received 28 views. For similar materials see /class/215368/cis511-university-of-pennsylvania in Computer Information Technology at University of Pennsylvania.
Reviews for THEORYOFCOMPUTATION
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/28/15
318511 Introduction to the Theory of Computation Formal Languages and Automata Models of Computation Jean Gallier February 8 2010 Chapter 1 Basics of Formal Language Theory 11 Generalities Motivations Problems In this part of the course we want to understand 0 What is a language 0 How do we de ne a language 0 How do we manipulate languages combine them 0 What is the complexity of a language Roughly there are two dual Views of languages A The recognition point View B The generation point of View 4 CHAPTER 1 BASICS OF FORMAL LANGUAGE THEORY No matter how we View a language we are typically con sidering two things 1 The syntax ie what are the legal strings in that language what are the grammar rules 2 The semantics of strings in the language ie what is the meaning or interpretation of a string The semantics is usually a lot more interesting than the syntax but unfortunately much more dif cult to deal with Therefore sorry we will only be dealing with syntax In A we typically assume some kind of black box M an automaton that takes a string w as input and returns two possible answers Yes the string in is accepted which means that in be longs to the language L that we are trying to de ne N0 the string in is rejected which means that w does not belong to the language L 11 GENERALITIES M 0 TI VATI ON S PROBLEMS 5 Usually the black box M gives a de nite answer for every input after a finite number of steps but not always For example a Turing machine may go on computing forever and not give any answer for certain strings not in the language This is an example of undecidabz lity The black box may compute deterministically or non determz m stz cally which means roughly that on input 111 the machine M is allowed to try different computations and to ignore failing computations as long as there is some successful computation on input 111 This affects greatly the complexity of recognition ie how many steps it takes to process 111 6 CHAPTER 1 BASICS OF FORMAL LANGUAGE THEORY Sometimes a nondeterrninistic version of an automaton turns out to be equivalent to the deterministic version although with different complexity This tends to happen for very restrictive rnodelsiwhere nondeterrninisrn does not help or for very powerful rnodelsiwhere again nondeterrninisrn does not help but because the deterministic model is already very powerful We will investigate autornata of increasing power of recog nition 1 Deterrninistic and nondeterrninistic finite autornata DFA s and NFA s their power is the same 2 Pushdown autornata PDA s and deterrninstic push down autornata DPDA s here PDA gt DPDA 3 Deterrninistic and nondeterrninistic Turing rnachines their power is the same 4 If time permits we will also consider some restricted type of Turing machine known as LBA linear bounded autornaton 11 GENERALITIES M 0 TI VATI ON S PROBLEMS 7 In B we are interested in formalisms that specify a language in terms of rules that allow the generation of legal strings The most common formalism is that of a formal grammar Remember 0 An automaton recognizes or accepts a language 0 a grammar generates a language 0 grammar is spelled With an a not with an o The plural of automat on is automata not automatons For good Classes of grammars it is possible to build an automaton Mg from the grammar G in the Class so that MG recognizes the language LG generated by the grammar G 8 CHAPTER 1 BASICS OF FORMAL LANGUAGE THEORY However grammars are nondeterministic in nature Thus even if we try to avoid nondeterministic automata we usually can t escape having to deal with them We will investigate the following types of grammars the so called Chomsky hierarchy and the corresponding fam ilies of languages 1 Regular grammars type 3 languages 2 Context free grammars type 2 languages 3 The recursively enumerable languages or re sets type O languages 4 If time permit context sensitive languages type 1 languages Miracle The grammars of type 1 2 3 4 corre spond exactly to the automata of the corresponding type 11 GENERALITIES M 0 TI VATI ON S PROBLEMS 9 Furthermore there are algorithms for converting gram mars to the corresponding automata and backward al though some of these algorithms are not practical Building an automaton from a grammar is an important practical problem in language processing A lot is known for the regular and the context free grammars but there is still room for improvements and innovations There are other ways of de ning families of languages for example Inductive closures In this style of de nition a collection of basic atomic languages is speci ed some operations to combine lan guages are also speci ed and the family of languages is de ned as the smallest one containing the given atomic languages and closed under the operations 10 CHAPTER 1 BASICS OF FORMAL LANGUAGE THEORY Investigating closure properties for example union in tersection is a way to assess how robust or complex a family of languages is Well it is now time to be precise 12 Alphabets Strings Languages Our View of languages is that a language is a set of strings In turn a string is a nite sequence of letters from some alphabet These concepts are de ned rigorously as fol lows De nition 121 An alphabet Z is any nite set We often write 2 0L17 ak The ai are called the symbols of the alphabet 12 ALPHABETS STRINGS LANGUAGES 11 Examples 21a Z a b e Z 01 A string is a nite sequence of symbols Technically it is convenient to de ne strings as functions For any integer n 2 1 let lnl172w7n and for n 0 let 0 ll De nition 122 Given an alphabet Z a string over 2 or simply a string of length n is any function u gt Z The integer n is the length of the string u and it is denoted as When n 0 the special string u 0 gt Z of length 0 is called the empty string or null string and is denoted as e 12 CHAPTER 1 BASICS OF FORMAL LANGUAGE THEORY Given a string u gt Z of length n 2 1 is the i th letter in the string u For simplicity of notation we denote the string u as u u1u2un with each 211 E E For example if E a b and u 3 gt Z is de ned such that 211 a 212 b and 213 a we write it aba Strings of length 1 are functions u 1 gt 2 simply picking some element 211 ai in 2 Thus we will identify eyery symbol ai E E with the corresponding string of length 1 The set of all strings over an alphabet 2 including the empty string is denoted as 2 12 ALPHABETS STRINGS LANGUAGES 1 Observe that when E Q then 0 When 2 y Z the set 2 is countably in nite Later on we will see ways of ordering and enumerating strings Strings can be juxtaposed or concatenated De nition 123 Given an alphabet 2 given any two strings u gt Z and v gt Z the concatenation it 1 also written an of u and v is the string M m n gt 2 de ned such that Wmi an irigz gm i vZ m ifm1 t mn In particular ue en n It is immediately veri ed that Mew Thus concatenation is a binary operation on 2 which is associative and has 6 as an identity 14 CHAPTER 1 BASICS OF FORMAL LANGUAGE THEORY Note that generally an 7A 1m for example for u a and v b Given a string u E 2 and n 2 0 we de ne u as follows uni e ifn0 i u 1u ifnZl Clearly ul u and it is an easy exercise to ShOW that for all n 2 0 12 ALPHABETS STRINGS LANGUAGES 15 De nition 124 Given an alphabet 2 given any two strings u v E 2 we de ne the following notions as fol lows u is a pre x ofv i there is some 3 E 2 such that vuy u is a su x of v i there is some 1 E 2 such that U L u u is a substi ing of v i there are some 51 y E 2 such that v way We say that u is a proper pre x su x subsiring 0f 1 i u is a pre x suf x substring of v and u y v 16 CHAPTER 1 BASICS OF FORMAL LANGUAGE THEORY Recall that a partial ordering g on a set S is a binary relation g g S X S which is re exive transitive and antisymmetric The concepts of pre x suf x and substring de ne binary relations on 2 in the obvious way It can be shown that these relations are partial orderings Another important ordering on strings is the lexicographic or dictionary ordering 12 ALPHABETS STRINGS LANGUAGES 17 De nition 125 Given an alphabet 2 G1 ak assurned totally ordered such that a1 lt a2 lt lt ak given any two strings uv E 2 we de ne the lexico graphic ordering j as follows if v uy for some 3 E 2 or u j v if u swig1 majz and a lt a for some 51 y z E 2 It is fairly tedious to prove that the lexicographic ordering is in fact a partial ordering In fact it is a total ordering which means that for any two strings u v E 2 either u j v or v j u The reversal MB of a string w is de ned inductively as follows R e E 7 uaR auR where a E 2 and u E 2 18 CHAPTER 1 BASICS OF FORMAL LANGUAGE THEORY It can be shown that avR vRaR Thus R R R una1 and when al 6 Z we have U1anRana1 We can now de ne languages De nition 126 Given an alphabet Z a language over 2 07 simply a language is any subset L of 2 If E y Z there are uncountably many languages We will try to single out countable tractable families of languages We will begin with the family of regular lan guages and then proceed to the contextfree languages We now turn to Operations on languages 13 OPERATIONS ON LANGUAGES 19 13 Operations on Languages A way of building more complex languages from simpler ones is to combine them using various operations First we review the set theoretic operations of union intersec tion and complementation Given some alphabet Z for any two languages L1 L2 over 2 the union L1 U L2 of L1 and L2 is the language L1UL2UJEZ UJEL1 OI UJELQ The intersection L1 L2 of L1 and L2 is the language L1HL2UJEZ w L1 and MELQ The di erence L1 L2 of L1 and L2 is the language L1 L2UJEZ UJEL1 and The difference is also called the relative complement 20 CHAPTER 1 BASICS OF FORMAL LANGUAGE THEORY A special case of the difference is obtained when L1 2 in which case we de ne the complement E of a language L as fw Zlw L The above operations do not use the structure of strings The following operations use concatenation De nition 131 Given an alphabet Z for any two lan guages L1 L2 over 2 the concatenation L1L2 of L1 and L2 is the language L1L2 w E 2 l 3n 6 L1 31 6 L2 w no For any language L we de ne L as follows L0 6 Ln1 LnL 13 OPERATIONS ON LANGUAGES 21 The following properties are easily veri ed 109 L Q Le L ElL L7 L1 U 6L2 L1L2 U L2 L1ltL2 U 1ng U L1 LnL LL In general L1L2 y L2L1 So far the operations that we have introduced except cornplernentation since I 2 L is in nite if L is nite and Z is nonempty preserve the niteness of languages This is not the case for the next two operations 22 CHAPTER 1 BASICS OF FORMAL LANGUAGE THEORY De nition 132 Given an alphabet Z for any lan guage L over 2 the Kleene cl08m e L of L is the language L U L 7120 The Kleene cl08m e L of L is the language L U L n21 T hus L is the in nite union LL0UL1UL2UUL U and L is the in nite union LL1UL2UUL U Since L1 L both L and L contain L 13 OPERATIONS ONLANGUAGES 23 In fact Lw Z 37121 Elm E E L wu1quot39una and since L0 e L UUJEZ 37121 3m 6 L3un E L wu1un Thus the language Lquot always contains 6 and we have Lquot L U 24 CHAPTER 1 BASICS OF FORMAL LANGUAGE THEORY However if e e L then 6 e L The following is easily shown 9 6 L UL L L LL L The Kleene Closures have many other interesting proper ties Hornornorphisrns are also very useful Given two alphabets Z A a homomorphism h 2 gt Aquot between 2 and Aquot is a function h 2 gt Aquot such that Mew huhv for all u v E 2 13 OPERATIONS ON LANGUAGES 25 Letting u v e we get M6 WW6 which implies that Why Me E If E 011 ak it is easily seen that h is completely determined by Mal Mak Why Example 2 a b C A 01 and Ma 01 Mb 011 110 0111 For example habbc 010110110111 26 CHAPTER 1 BASICS OF FORMAL LANGUAGE THEORY Given any language L1 Q 2 we de ne the image hL1 of L1 as E A l u E Given any language L2 Q Aquot we de ne the inverse image h1L2 of L2 as h1L2 u E 2 l E We now turn to the rst formalism for de ning languages Deterministic Finite Automata DFA s Chapter 2 Regular Languages 21 Deterministic Finite Automata DFA s First we de ne what DFA s are and then we explain how they are used to accept or reject strings Roughly speak ing a DFA is a nite transition graph whose edges are labeled with letters from an alphabet Z The graph also satis es certain properties that make it deterministic Basically this means that given any string w starting from any node there is a unique path in the graph parsing the string w 28 CHAPTER 2 REGULAR LANGUAGES Example 1 A DFA for the language L1 abV ababa L1 ab abab ababab 011 Input alphabet Z a b State set Q1 0 1 2 3 Start state 0 Set of accepting states F1 Transition table function 61 color to oar ng wwmwv Note that state 3 is a trap state or dead state 21 DETERMINISTIC FINITE AUTOMATA DFA S 29 Example 2 A DFA for the language L2 ab L1 U 6 L2 6 ab abab ababab ab Input alphabet Z a b State set Q2 012 Start state 0 Set of accepting states F2 Transition table function 62 or to mum 9 momw State 2 is a trap state or dead state 30 CHAPTER 2 REGULAR LANGUAGES Example 3 A DFA for the language L3 a babb Note that L3 consists of all strings of as and Us ending in abb Input alphabet Z a b State set Q3 0 1 2 3 Start state 0 Set of accepting states F3 Transition table function 63 CONN to r w w w tg OWNOG Is this a minimal DEA 21 DETERMINISTIC FINITE AUTOMATA DFA S Figure 23 DFA for a7babb 31 32 CHAPTER 2 REGULAR LANGUAGES De nition 211 A deterministic nite automaton or DFA is a quintuple D Q E 6 go E where 0 Z is a nite input alphabet c Q is a nite set of states 0 F is a subset of Q of nal or accepting states 0 go 6 Q is the start state or initial state o 6 is the transition function a function 6QgtltZ gtQ 21 DETERMINISTIC FINITE AUTOMATA DFA S 33 For any state 10 E Q and any input a E Z the state q 619 a is uniquely determined Thus it is possible to de ne the state reached from a given state 10 E Q on input w E 2 following the path speci ed by w Technically this is done by de ning the extended transition function 6 Q gtlt 2 gt Q De nition 212 Given a DFA D QZ6q0F the extended transition function 6Q X 2 gt Q is de ned as follows 629 6 29 619 ua 66p u a Where a E Z and u E 2 It is immediate that 6pa 619 a for a E Z The meaning of 619 w is that it is the state reached from state 10 following the path from p speci ed by w 34 CHAPTER 2 REGULAR LANGUAGES It is also easy to show that 5197 W 55p u v We can now de ne how a DEA accepts 0r rejects a string De nition 213 Given a DEA D QZ6q0F the language LD accepted 07 recognized by D is the language LD w E 2 l 6q0w E F Thus a string w E 2 is accepted iff the path from go on input w ends in a nal state We now come to the rst of several equivalent de nitions of the regular languages 21 DETERMINISTIC FINITE AUTOMATA DFA S 35 Regular Languages Version 1 A language L is a regular language if it is accepted by some DFA Note that a regular language may be accepted by many different DFAs Later on we will investigate how to nd minimal DFA s For a given regular language L a min imal DFA for L is a DFA with the smallest number of states among all DFA s accepting L A minimal DFA for L must exist since every nonempty subset of natural numbers has a smallest element In order to understand how complex the regular languages are we will investigate the closure properties of the reg ular languages under union intersection complementa tion concatenation and Kleene It turns out that the family of regular languages is closed under all these operations For union intersection and complementation we can use the cross product construc tion Which preserves determinism 36 CHAPTER 2 REGULAR LANGUAGES However for concatenation and Kleene there does not appear to be any method involving DFA s only The way to do it is to introduce nondeterrninistic nite autornata NFA s 22 The Crossproduct Construction Let Z a17 am be an alphabet Given any two DFA s D1 Q1 2 61 q071 F1 and D2 Q2 2 62 q072 F2 there is a very useful construc tion for showing that the union the intersection or the relative complement of regular languages is a regular lan guage Given any two languages L1 L2 over 2 recall that LlUL2UJ Z UJ L1 OI MELQ Ll L2w ZleL1 and MEI2 L1 L2UJEZ UJ L1 and 22 THE CROSS PRODUCT CONSTRUCTION 37 Let us rst explain how to constuct a DFA accepting the intersection L1 L2 Let D1 and D2 be DFA s such that L1 LD1 and L2 LD2 The idea is to construct a DFA simulating D1 and D2 in parallel This can be done by using states which are pairs 191 192 6 Q1 gtlt Q2 Thus we de ne the DFA D as follows D Q1 gtlt Q27 2767 q017q027 F1 gtlt F27 where the transition function 6 Q1 gtlt Q2 X Z gt Q1 gtlt Q2 is de ned as follows 191192 a 51091701 520927 01gt for all 191 6 621102 E Q2 and a E 2 Clearly D is a DFA since D1 and D2 are Also by the de nition of 6 we have 6p17p27 w lt61kp17w7 6312927110 for all 191 6 621102 E Q2 and w E 2 38 CHAPTER 2 REGULAR LANGUAGES Now we have w E LD1 LD2 E w E LD1 and w E LltD2gt7 1E 5119047111 E F1 and 5310727111 E 1727 E lt6T90717w75 qa27 E F1 gtlt F2 1E 5qo1qo2 w E F1 gtlt F27 iff w e LD Thus LD LD1 m M192 We can now modify D very easily to accept LD1 U LD2 We change the set of nal states so that it becomes F1 gtlt Q2 U Q1 gtlt F2 Indeed w E LD1 U LD2 iff w E LD1 or w E LD2 iff 61 q071w E F1 or 63q072 w E F2 HT 51 Qo17wa5 qa2aw E F1 gtlt Q2 U Q1 gtlt F2 HT 6ltQO717QO727 711 E F1 gtlt Q2 U Q1 gtlt F2 iff w E LD Thus LD LD1 u LD2 22 THE CROSS PRODUCT CONSTRUCTION 39 We can also modify D very easily to accept LD1 LD2 We change the set of nal states so that it becomes F1 gtlt Q2 F2 Indeed w E LD1 LD2 iff w E LD1 and w e LD2 iff 6fltq071w 6 F1 and 63q072w e F2 iff 5lQO17w75 QO27w E F1 gtlt Q2 F2 HT 5CIO17 I027U1 F1 gtlt Q2 F2 iff w E LD Thus LD LD1 M192 In all cases if D1 has 711 states and D2 has 712 states the DFA D has 711712 states 40 CHAPTER 2 REGULAR LANGUAGES 23 Morphisms FMaps BMaps and Homomorphisms of DFA S A map between DFA s is a certain kind of graph ho momorphism The following De nition is adapted from Eilenberg De nition 231 Given any two DFA s D1 62172751790475 and D2 6227275279027172 a morphism h D1 gt D2 of DFA s is a function h Q1 gt Q2 satisfying the following conditions 1 h51p7 1 620109 a for all p 6 Q1 and all a E Z 2 hfqm 902 An F map 0f DFA s for short a map is a morphism of DFA s h D1 gt D2 that satisfies the condition 3a Q F2 A Bmap 0f DFA s is a morphism of DFA s h D1 gt D2 that satisfies the condition 3b h1F2 Q F1 23 MORPHISMS F MAPS B MAPS AND HOMOMORPHISMS OF DFA S 41 A proper homomorphism of DFA 8 for short a homo morphism is an F map of DFA s that is also a B map of DFA s Now for any function ch gt Y and any two subsets A g X and B g Y fA g B if A g f 1B Thus 3a 85 3b is equivalent to the condition so h 1F2 F1 Note that the condition for being a proper homomor phism of DFA s is not equivalent to ME F2 It forces hF1 F2 hQ1 and furthermore for every p E Q1 Whenever hp 6 F2 then p 6 F1 The reader should check that if f D1 gt D2 and 9192 gt D3 are morphisms resp F map resp B map then 9 o f D1 gt D3 is also a morphism resp F map resp B map 42 CHAPTER 2 REGULAR LANGUAGES Remark In previous versions of these notes an F map was called simply a map and a B map was called an F 1 map Over the years the old terminology proved to be confusing We hope the new one is less confusing Note that an F map or a B map is a special case of the concept of simulation of automata A proper homomor phism is a special case of a bisimulatz on Bisimulations play an important role in real time systems and in con currency theory The main motivation behind these de nitions is that when there is an F map h D1 gt D2 somewhow D2 simulates D1 and it turns out that LD1 g LD2 When there is a B map h D1 gt D2 somewhow D1 simulates D2 and it turns out that LD2 g LD1 When there is a proper homomorphism h D1 gt D2 somewhow D1 bisimulates D2 and it turns out that LD2 LD1 23 MORPHISMS F MAPS B MAPS AND HOMOMORPHISMS OF DFA S 43 A DFA morphism resp F map resp B map f D1 gt D2 is an isomorphism iff there is a DFA mor phism resp F map resp B map gD2 gt D1 so that gofidD1 and fogidD2 The map 9 is unique and it is denoted f l The reader should prove that if a DFA F map is an isomorphism then it is also a proper homomorphism and if a DFA B map is an isomorphism then it is also a proper homo morphism If h D1 gt D2 is a morphism of DFA s it is easily shown by induction on the length of w that M51129 w 531 w for all p 6 Q1 and all w E 2 As a consequence we have the following Lemma 44 CHAPTER 2 REGULAR LANGUAGES Lemma 232 If h D1 gt D2 is an F map of DFA s then LD1 g LD2 If h D1 gt D2 is a Bmap of DFA s then LD2 Q LD1 Finally if hD1 gt D2 is a proper homomorphism of DFA s then LltDlgt M02 A DEA is accessible or trim if every state is reachable from the start state A morphism resp F map B map h D1 gt D2 is sur jective if hQ1 Q2 It can be shown that if D1 is trim then there is a most one morphism h D1 gt D2 resp F map B map If D2 is also trim and we have a morphism h D1 gt D2 then h is surjectiye It can also be shown that a minimal DFA DL for L is characterized by the property that there is unique surjec tiye proper homomorphism h D gt DL from any trim DEA D accepting L to DL 23 MORPHISMS F MAPS B MAPS AND HOMOMORPHISMS OF DFA S 45 Another useful notion is the notion of a congruence on a DFA De nition 233 Given any DFA D Q 264017 a congruence E on D is an equiva lence relation E on Q satisfying the following conditions 11fp E q then 6pa E 6qa for all pq E Q and all a E Z 21prqandpEFthenq Fforallpq Q It can be shown that a proper homomorphism of DFA s h D1 gt D2 induces a congruence Eh on D1 de ned as follows 29 Eh q iff Mp hm Given a congruence E on a DFA D we can define the quotient DFA D E and there is a surjectiye proper homomorphism 7r D gt D E We will come back to this point when we study minimal DFA s 46 CHAPTER 2 REGULAR LANGUAGES 24 Nondeteterministic Finite Automata NFA S NFA s are obtained from DFA s by allowing multiple tran sitions from a given state on a given input This can be done by de ning 6p a as a subset of Q rather than a single state It Will also be convenient to allow transitions on input 6 We let 2Q denote the set of all subsets of Q including the empty set The set 2Q is the power set of Q We de ne NFA s as follows 24 NONDETETERMINISTIC FINITE AUTOMATA NFA S 47 Example 4 A NFA for the language L3 a babb Input alphabet Z a b State set Q4 0 1 2 3 Start state 0 Set of accepting states F4 Transition table 64 Figure 24 NFA for a7babb 48 CHAPTER 2 REGULAR LANGUAGES Example 5 Let Z 0L17 an let L31 w E 2 l w contains an odd number of as andlet LnLoLiomoLg The language Ln consists of those strings over 2 that contain an odd number of some letter ai E 2 Equivalently 2 Ln consists of those strings over 2 with an even number of every letter ai E 2 It can be shown that that every DFA accepting Ln has at least 2 states However there is an NFA with 271 1 states accepting Ln and even With 271 statesl 24 NONDETETERMINISTIC FINITE AUTOMATA NFA S 49 De nition 241 A nondeterniinistic nite automa ton or NFA is a quintuple N Q 2640177 where 0 Z is a finite input alphabet c Q is a finite set of states 0 F is a subset of Q of nal 07 accepting states 0 go 6 Q is the start state or initial state 0 6 is the transition function a function 6Q gtlt EU gt 2Q For any state 10 E Q and any input a E E U 6 the set of states 619 a is uniquely determined We write q 6 50 Given an NFA N QZ6q0F we would like to de ne the language accepted by N and for this we need to extend the transition function 6 Q X E U gt 2Q to a function 6 Q X 2 gt 2Q 50 CHAPTER 2 REGULAR LANGUAGES The presence of e transitions ie when q E 6pe causes technical problems and to overcome these prob lems we introduce the notion of e closure 25 e Closure De nition 251 Given an NFA N QZ6q0F with e transitions for every state 10 E Q the eclosure ofp is set e closurep consisting of all states q such that there is a path from p to q whose spelling is 6 This means that either q p or that all the edges on the path from p to q have the label 6 We can compute e closurep using a sequence of approx irnations as follows De ne the sequence of sets of states e cloZpZZo as follows E010019 p EClO 1p e cloZp U q E Q l 35 E e cloZp q 6 63 25 e CLOSURE 51 Since e clozp Q ClO 1p e clozp Q Q for all 2 Z 0 and Q is nite there is a smallest Z say to such that 6010mm 6010 01p and it is immediately veri ed that e closurep e cloi0p When N has no e transitions ie when 619 6 Z for all p E Q which means that 6 can be Viewed as a function 6 Q X Z gt 2Q we have e closurep It should be noted that there are more ef cient ways of computing e closurep for example using a stack basi cally a kind of depth rst search We present such an algorithm below It is assumed that the types NFA and stack are de ned If n is the number of states of an NFA N we let eclotype array1n of boolean 52 CHAPTER 2 REGULAR LANGUAGES function eclosurdN NFA p integer eclotype begin var eclo eclotype q s integer st stack for each q E setstatesN d0 ecl0q false endfor ecl0p true st empty trans deltatableN st push8tp while st 7A emptystack d0 q WOW for each s E transq e do if ecl05 false then ecl05 true st push8t 3 endif endfor endwhile eclosure eclo end This algorithm can be easily adapted to compute the set of states reachable from a given state 10 in a DEA or an NFA 25 E CLOSURE 53 Given a subset S of Q we de ne e closureS as e closureS U e closurep 1963 When N has no e ti ansitions we have e closureS S We are now ready to de ne the extension 6 Q X 2 gt 2Q of the transition function 6 Q X E U gt 2Q 54 CHAPTER 2 REGULAR LANGUAGES 26 Converting an NFA into a DFA The intuition behind the de nition of the extended transi tion function is that 619 w is the set of all states reach able from p by a path Whose spelling is 111 De nition 261 Given an NFA N QZ6q0F with e transitions the extended transition function 6 Q X 2 gt 2Q is de ned as follows for every p E Q every n E 2 and every a E Z 6p e e closurep 619 aa e closure U 63 a 566p7u The language LUV accepted by an NFA N is the set LN w E 2 l 6q0w H F y Ql 26 CONVERTING AN NFA INTO A DFA 55 We can also extend 6 Q X 2 gt 2Q to a function 3 2Q X 2 gt 2Q de ned as follows for every subset S of Q for every 1116 33 111 U 619 w pES Let Q be the subset of 2Q consisting of those subsets S of Q that are e closed ie such that S e closureS If we consider the restriction AQgtltZ gtQ of 3 2Q X 2 gt 2Q to Q and Z we observe that A is the transition function of a DFA Indeed this is the transition function of a DFA accepting LN It is easy to show that A is de ned directly as follows on subsets S in Q AS a e closureU 63 a 56S 56 CHAPTER 2 REGULAR LANGUAGES Then the DEA D is de ned as follows D Q E A e closureg0 F wherefS Q S Fy Ql It is not difficult to show that LD LN that is D is a DEA accepting LN Thus we have converted the NFA N into a DEA D and gotten rid of e transitions Since DFA s are special NFA s the subset construction shows that DFA s and NFA s accept the same family of languages the regular languages version 1 although not with the same complexity The states of the DEA D equivalent to N are e closed subsets of Q For this reason the above construction is often called the subset construction It is due to Rabin and Scott Although theoretically fine the method may construct useless sets S that are not reachable from the start state e closureg0 A more economical construc tion is given next 26 CONVERTING AN NFA INTO A DFA 57 An Algorithm to convert an NFA into a DFA The subset construction Given an input NFA N Q E 6 go F a DFA D K E A S0 F is constructed It is assumed that K is a linear array of sets of states S Q Q and A is a 2 dirnensional array Where AM a is the target state of the transition from K S on input a with S E K and a E 2 S0 e closureq0 total 1 K1 S0 marked 0 while marked lt total do marked marked 1 S Kmarked for each a E 2 do U Uses s a T e closureU if T g K then total total 1 Kt0tal T endif Amarked a c T endfor endwhile JrS K S F 58 CHAPTER 2 REGULAR LANGUAGES Let us illustrate the subset construction on the NFA of Example 4 A NFA for the language L3 a babb Transition table 64 b 0 1 0 2 3 Q 888 Q 0 l 2 3 Set of accepting states F4 a7b Figure 25 NFA for a7babb 26 CONVERTING AN NFA INTO A DFA 59 The pointer gt corresponds to marked and the pointer gt to total Initial transition table A gt narnes states a b B 0 Just after entering the While loop narnes states a b gt gt A 0 After the rst round through the While loop narnes states a b A 0 B A gt B 0 1 After just reentering the While loop narnes states a b A 0 B gt gt B 0 1 After the second round through the While loop narnes states a b A 0 B A gt B 01 B C gt 0 02 60 CHAPTER 2 REGULAR LANGUAGES After the third round through the While loop names states A 0 a B B 01 B B UQDgt After the fourth round through the While loop names states a b A 0 B A B 0 1 B G G 0 2 B D gt gt D 03 B A This is the DEA of Figure 23 except that in that example A B G D are renamed 0 1 2 3 Figure 26 DEA for ababb
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'