### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# FORMAL LANG & AUTM CompSci 162

UCI

GPA 3.59

### View Full Document

## 11

## 0

## Popular in Course

## Popular in ComputerScienence

This 25 page Class Notes was uploaded by Hertha Tremblay on Saturday September 12, 2015. The Class Notes belongs to CompSci 162 at University of California - Irvine taught by James Arvo in Fall. Since its upload, it has received 11 views. For similar materials see /class/201900/compsci-162-university-of-california-irvine in ComputerScienence at University of California - Irvine.

## Reviews for FORMAL LANG & AUTM

### 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/12/15

Chapter 5 Finite Automata This chapter introduces the notions of deterministic and nondeterministic nite automata and explores connections among several classes of languages Regu ar FA cceptable and NFA acceptablei Along the way we describe an important algorithm for converting an NFA into an equivalent DFA that is a DFA that accepts the very same language as the NFA We shall also derive a very powerful tool commonly known as the Pumping Lemma which will allow us to prove that certain languages are inherently too complex for any DFA or NFA to recognize 51 Deterministic Finite Automata An automaton1 is a machine that behaves according to a precise set of instructions A nite automa ton2 is a mathematical abstraction of a speci c type of simple machine one with extremely limited capabilities but with many theoretical and practical applications We shall rst study the deter ministic nite automaton or DFA in which every action of the machine is uniquely determined and then the nondeterministic version or NFA in which some actions of the machine may be chosen arbitrarily Finite automata3 are machines that can recognize languages possessing relatively simple patterns The machine reads the symbols of a string which we imagine to be printed on a tape that extends in nitely to the right We refer to each location on the tape where a symbol can be written as a cell All the cells following the last symbol of the string are considered to be blank See Figure Sill Beginning in its initial state or start state the machine reads the tape from the leftmost symbol moving a read head along it in discrete steps one symbol at a time Every time the machine reads a symbol two things happen simultaneously 1 The state of the machine changes based on its current state and the symbol that was just read 1Automaton pronounced awe TOMeuhe TA WN is the singular form of automata 2Another common name for a nite automaton is a nite state machine 3The plural of automaton is pronounced aweTOMeuhetuh not autoeMA YTA There is no auto is automata 51 52 CHAPTER 5 FINITE AUTOMATA 2 The read head moves to the right so that it is positioned over the next symbol on the tape or the rst blank cell following the string if the last symbol of the string has just been read This process continues until the last symbol of the string has been read at which point the read head is positioned over the blank cell just past the end of the string The state that the machine is left in at this point can be used to classify the string in particular the machine distinguishes between strings that leave the machine in an accept state and those that do not The deterministic version of such a machine is formally speci ed by the 5tuple E Q 40 A 6 where H E is a nite nonempty set called the alphabet Q is a nite nonempty set of states go is the initial state the state of the machine before reading each stringi F90 A Q Q is a special set of states called the accept states 5 6 is the transition function that maps Q X E to Notice that there is no explicit mention of the tape or read head in this formalismi The idea of an in nite tape arises from the fact that the input string is not part of the machine de nition instead we conceive of the machine as being capable of processing arbitrarily long albeit nite input strings that are written on its tape The operation of this machine can also be given a completely formal de nition that captures the intuitive description given above For this we will require the notion of a con guration or instanta neous snapshot of the machine and a yields relation which will de ne the sequence of con gurations that a machine enters as it operates We rst provide some basic notation and a convenient means of representing a DFA diagrammatically Let M denote the machine 2 Q 40 A 6 and let w E 2 be some string We shall use the notation SM to denote the set of states of machine M after reading string w of course for a DFA this set will always be a singleton as it is always left in precisely one state If the single element of SM is in the set A of the accept states we say that the machine accepts or recognizes the string wi We can also state this condition as SM N A f 0 The set of all recognized strings constitutes a language associated with Mi More precisely we de ne M 5 w e 2 SMw nA y 0 51 to be the language accepted or recognized by the machine Mi4 Such languages form an important class so we shall give them a special namei De nition 11 A language is called DFAacceptable if and only if a DFA Deterministic Finite Automaton can be constructed that recognizes it 4We could have also written the criterion in Equation 51 as 8Mw C A While these de nitions are equivalent in the case of DFAs we will nd that they are not equivalent for NFAs In particular 5M N A 74 Q generalizes immediately to NFAs while 5M C A does not 5 H DETERMINISTIC FINITE AUTOMATA 53 in 111 a e 4 p p read head tape cell nite control 391 rejectindicator O um O acceptindicator Figure 51 Conceptually a nite automaton consists of a nite control a read head and an input tape that is in nite in one direction by convention it is always drawn so that it is in nite to the right In each discrete step the read head moves exactly one cell to the right until the end of the input string is reached After each discrete transition one of the two indicator lights is lit up Once the string has been read we say that the machine accepts or rejects the string depending on which of the two lights is left on The transition function 6 Q X E A Q de nes the behavior of the DFA as the tape is being read If the machine is in state 4 and the symbol 8 is read the machine enters state 64 3 This transition can and usually does in uence the states entered as subsequent symbols are rea As a simple example consider the language ab over the alphabet E a b We can define a simple DFA that accepts this language using only three states Q 40 L11 42 where go is the start state and both go and q1 are accept states thus A 4041 The transition function 6 C Q X E of this machine can be de ned as follows 6 a b 40 40 41 41 42 41 42 42 42 The state qg is known as a trap state since the machine never leaves that state once it enters it De ning the transition function 6 using a table as above can be extremely cumbersome for more complex machines Fortunately there is a much more intuitive yet complete representation available for defining such machines namely state diagrams 511 State Diagrams Figure 52 shows a state diagram for a DFA that accepts a simple language over the alphabet a b that includes strings such as aba and baabb Each state 4 is depicted by a circle with the label q and each transition 64 a q is depicted by an arrow from state 4 to state 4 with the label a The initial state is indicated with an inwardpointing arrow with no label and the accept states are indicated by double circles An arrow with label a leaving state 4 indicates which state to move to upon reading an a from the tape when the machine is in state 4 Different strings will cause the machine to follow different paths through the directed graph of states starting from the initial state each time 54 CHAPTER 5 FINITE AUTOMATA Figure 52 A state diagram for a DFA that accepts a simple language over the alphabet ab Here state qo is the initial state states 12 and 13 are accept states and state 14 is a noneaccepting trap More formally the machine would be written as the 5tuple E Q 40 A 6 where E a 12 Q 107 117 12 43744 A 127 13 5 407a7427 40757407 417 41 417177 43 427a7437 427 by 41 437a7447 437117497 447a7447 447 by 44 Here each ordered pair qa q de ned by the function 6 Q X E A Q has been abbreviated to q a 4 Since 6 is a function defined on Q X E as a set it must contain exactly one tuple for every q a E Q X E In terms of the state diagram this means that every state is represented by a circle and each circle must have an arrow leaving it for each letter in the alphabet The state diagram is actually a complete specification of the DFA but one that is far easier to think about Given the state diagram of a DFA we can always construct the corresponding 5tuple and vise versa 512 Con gurations and the Yields Relation Once a symbol is read it is never considered by the machine again because the read head moves only to the rights Consequently when a symbol is read its in uence is recorded solely in the machine state that is entered nextl All subsequent computation is completely determined by the current state of the machine 4 and the unread portion of the tape ii We combine this information into an ordered pair q u called the con guration of the machine the sequence of configurations completely describes the behavior of the machine on a given string lf 6qa q and w au where w and u are strings in 2 then one can think of 6 as defining a transformation from one configuration to another which we write as 47w f 4 52 52 NONDETERMINISM 55 which is read con guration 410 yields con guration q u in one step77 The symbol k actually represents a binary relation on Q X 2 which is formally de ned by 417101 F 427102 ltgt 5417a 42 A M aw2l7 where wl and 112 are strings in 2 and a E 2 Here 112 can be any string at all including the empty string because the next transition made by the machine is completely determined by the current state ql and the current symbol a although subsequent transitions will depend on 102 It follows that 417 b 42 ltgt 417 b 4271 for all strings u and v in 2 While fairly obvious this simple fact is one of the tools that allows us to reason formally about the behavior of a DFAl In particular the implication 417a b 4275 gt 417 aw F 42710 for any w E 2 will be a useful transformation in constructing formal proofs about DFAsl However we also need a way to reason about the composition of many steps in a computation To this end we de ne the reflexive transitive closure of the binary relation H i From the relation P we de ne a new relation P by forming the reflexive transitive closure of k which extends it to include all nite sequences of steps that the machine M can take That is for a given machine M the con guration ql u eventually reaches the con guration L12 v if and only if mw mm which we read as con guration q1u yields con guration q2v after zero or more steps of machine M More formally we may give an inductive de nition of this relation as 4111 k 427v 11711 l 427v 5 3 KQAm2eltw om m awrmmAwmiuwgt ma am am where u v and w are strings in 2 lmplication 53 makes the new relation an extension that is a superset of the old relation implication 54 makes the new relation reflexive and implication 55 makes the new relation transitive that is closed under compositionl Taken together these impli cations completely specify the binary relation k for a given machine Ml From this de nition it follows that w E M if and only if mWfW em for some 4 6 A 52 Nondeterminism A Nondeterministic Finite Automaton NFA is a generalization of a deterministic nite automaton DFA in which any given transition may be incompletely determined by the current state of the 56 CHAPTER 5 FINITE AUTOMATA a 0 a 0 b a 0 ab 0 a b C d e Figure 53 Four complete NFAs with E a b that demonstrate the generality of nondeterministic machines a missing transitions such as an arrow labeled a leaving state 1 b transitions with strings as labels not just single characters c null transitions which have empty strings as labels d simple ambiguous transitions and e more complex ambiguous transitions machine and the symbol currently under the read head for example there may be several equally valid alternatives to choose from or perhaps none at all The various possibilities are depicted in Figure 53 In contrast a DFA always has exactly one valid transition at each step of the computation When an ambiguous transition is encountered in a nondeterministic machine such as the situations depicted in d and e of Figure 53 we can imagine the machine behaving in one of several different ways 0 Random Selection The machine arbitrarily chooses one of the applicable transitions Sequential Search The machine follows each of the applicable branches one after the other to determine which states may ultimately be reached Parallel Search The machine clones itself as many times as necessary and follows all applicable branches simultaneously to determine which states may ultimately be reached 0 Consult an Oracle The machine consults an allknowing oracle which magically tells it the right transition to follow eg the transition that will ultimately lead it to an accept state i As it happens all of these interpretations will be equivalent when studying the possible behavior of such a machine without regard to time that is when we are concerned only with which outcomes are possible and when we disregard the number of steps the machine takes in reading a string on the tape As time will be irrelevant in our current discussion we may choose the interpretation that seems most helpful or intuitive in each situation There are exactly four ways in which the de nition of an NFA can differ from that of a DFA and all of them are generalizations of the DFA These are listed below and correspond to the simple machines shown in Figure 53 1 Not all transitions need be speci ed as in Figure 53a All unspeci ed transitions are un derstood to lead to a reject trap 52 NONDETERMINISM 57 2 Transitions may be labeled with sequences of symbols iiei strings as in Figure 5i3b as well as with single symbols Such transitions read an entire pre x from the tape as opposed to a single symbol 3 Transitions may be labeled with the null string as in Figure 5i3ci Such a transition leaves the read head xed while changing the state 4 There may be multiple transitions with the same label leaving a single state as in Figure 5i3d or otherwise equivalent paths leaving a single state as in Figure 53 e These generalizations require that we abandon the notion of a transition function since ambiguous transitions produce multiple values for example we would have both 6p a q and 6p a r in the example d of Figure 53 To remedy this we replace the function 6 with the relation A Thus an NFA is formally de ned to be a 5tuple 2Qq0A A where all of the symbols have the same meanings as in the DFA with the exception that A is now the transition relation on the set Q X 2 X Each 3tuple in this relation represents the current state the string labeling a transition and the state the transition leads to Notice that this one change accommodates all four of the generalizations abovei Let M denote an NFAi We shall say that M accepts or recognizes a string w E 2 if and only if there is some sequence of nondeterministic choices that M could make in processing w that would lead to an accept statei Equivalently M accepts w if and only if at least one of the clones generated via nondeterminism ends in an accept state It is easy to see how all of the interpretations of nondeterminism mentioned above lead to exactly the same conclusions regarding acceptance of strings As in the deterministic case we shall let SM denote the set of states that an NFA may be left in after reading the string w while this set will always be a singleton for a DFA in the case of an NFA it may have any number of elements including zero The elements of this set correspond to all possible states that can be reached by making different decisions while reading the string w This property leads to a slightly different notion of what it means for an NFA to accept a string We have the following de nitions for NFAs which parallel those for DFAsi De nition 12 Let machine M be an NFAi We say that M accepts a string w E 2 if and only if SM N A 3e 0 That is if and only if at least one sequence of choices can be made while reading the string that leaves the machine in an accept state after reading the string De nition 13 The language accepted or recognized by an NFA M 2 Q 40 A A is de ned to be the set w E 2 l SM N A 3e 0 which is denoted by M as in the deterministic casei De nition 14 A language is called NFAacceptable if and only if an NFA Nondeterministic Finite Automaton can be constructed that accepts it Clearly all DFAacceptable languages are also NFAacceptablei This follows immediately from the de nition of NFAs which are simply generalizations of DFAsi Thus every DFA is also a valid NFA one in which none of generalizations noted above are actually exploitedi 58 CHAPTER 5 FINITE AUTOMATA c Figure 54 A DFA that recognizes the language abquot Uacquot Nondeterminism is not intended to model randomness that may occur in actual machines such as quantum effects or hardware failuresi As we shall see nondeterminism is primarily a powerful theoretical tool it will allow us to prove things about nite automata that would otherwise be very cumbersome Nondeterminism is also a convenient notational devicei As a first concrete example of the utility of nondeterminism we note that it frequently allows for great economy in specifying machinesi Consider the DFA shown in Figure 54 which recognizes the simple language ab U ac over the alphabet abci Here we have labeled some of the transitions with sets as an abbreviation for multiple arrows that share the same beginning and ending states that is the set notation encodes parallel edges whereas a string of characters in an NFA encodes multiple edges that are in sequence77 Using the conventions of an NFA the same language can be recognized with a much simpler machine In the NFA shown in Figure 55 only three states suffice thanks to the conveniences afforded by nondeterminismi The trap has been removed by simply not specifying transitions that cannot lead to an accept state The resulting NFA has both fewer states and fewer transitionsi 53 FINITE AUTOMATA AND REGULAR LANGUAGES 59 Figure 55 An NFA that recognizes the language abquot U acquot Nondeterminism allows us to create such a machine using fewer states and transitions than the equivalent DFA 53 Finite Automata and Regular Languages We have now de ned several classes of languages either explicitly by giving a method for generating strings in the language eigi regular expressions or implicitly by constructing an automaton DFA or NFA that recognizes strings in the languages The classes we have de ned are ll Regular 2 DFAacceptable 3i NFAacceptable We will now demonstrate the these classes of languages are identical We will prove this by demonstrating three inclusions DFAacceptable Q Regular Regular Q NFAacceptable and NFA acceptable Q DFA acceptablei Each of these inclusions requires a different style of proof as illus trated in the following sections As a consequence of this equivalence we are justi ed in referring to the languages accepted by both DFAs and NFAs as regular 531 Regular Q NFAacceptable In this section we shall prove that the set of regular languages is a subset of the NFAacceptable languages In other words we will prove the following theorems Theorem 15 Every regular language is accepted by some NFA Proof We proceed by rst showing that the NFAacceptable languages include the null language and all the singleton languages then welll show that NFAacceptable languages possess all the necessary closure properties In particular welll show that if L1 and L2 are both NFAacceptable languages then so are the languages 60 CHAPTER 5 FINITE AUTOMATA Mz 0 a b Figure 56 Diagrammatic representations of two nite automata M1 and M2 either deterministic or none deterministic The only features that are relevant are the start states shown as single circles and the accept states shown as double circles Figure 57 New machines built from M1 and M2 that accept the a union of the two original languages the b concatenation and the c Kleene star of one of the original languages The dashed circles indicate states that are no longer accepting states 1 L1 0 L2 showing closure with respect to concatenation 2 L1 U L2 showing closure with respect to union 3 Llquot showing closure with respect to Kleene star First observe that an NFA with no accept states accepts the empty language Z and that for any a E E the machine shown in Figure 53a with p as initial state and q as an accept state accepts the singleton language a Thus all of the trivial regular languages are also NFA acceptablei We next demonstrate that all of the closure properties listed above also hold from which it will follow that all regular languages are NFAacceptablei To do this let us depict machines M1 and M2 which accept languages L1 and L2 respectively as in Figure 56 These simpli ed illustrations depict only the initial state and accepting states of which there may be any number Without loss of generality let us assume that the state labels appearing in the two diagrams are distinct Then from these two state diagrams we may construct state diagrams depicting new machines by adding states andor edges Figure 57a shows the state diagram for a machine that accepts the language L1 U L2 obtained by adding a new start state and two null transitions Figure 57b shows a similar construction for a machine that accepts the language L1 0 L2 Finally Figure 57c shows a machine that accepts the language L13 It is now easy to see that the NFAacceptable languages includes all of the regular languages since we can construct an NFA that accepts any language that can be represented by a regular expression 53 FINITE AUTOMATA AND REGULAR LANGUAGES 61 We need only echo each of the operations represented in the regular expression as an operation applied to machines the result will be an NFA that accepts exactly the same language as that represented by the regular expression 532 DFAacceptable Q Regular In this section we shall use induction to prove that the set of DFA acceptable languages is a subset of the regular languagesi That is we shall prove the following theoremi Theorem 16 The language accepted by every DFA is regular Proof Let M Q E 40 A 6 be a DFA with states Q 12 3 i i i n and initial state qo 1i Let Rk ij denote the set of strings that would cause M to pass from state i to state j without ever passing through a state labeled k or higher That is w E Rk ij if and only if machine M when started in state i would end up in state j after reading w but without ever leaving or entering states k through it with the possible exceptions of the rst or last transitions respectively Then M U Rn117m7 5 7 meA since Rn1 1721 excludes no intermediate states and all accepting states are accounted for We shall now show that Rkij is always regular using induction on hi As the base case observe that when k 1 the machine cannot pass through any intermediate states so we have R1031 a E E l 521 a J39 U Eiyi7 58 where Eij a when i j and Z otherwisei That is R1ij consists of all symbols for which there is a direct transition from i to j plus the empty string 5 in the case where i j s a nite language R1ij is clearly regular Now suppose that R1 i j R2 iji i i Rk ij are all regular as the inductive hypothesis and observe that Rk1i739 RkUJ U RAN CRIMSka 0PMle 59 It then follows from Equation 59 that Rk1ij is also regular as it consists of concatenations and a Kleene star of regular languagesi Finally we conclude from Equation 57 that M is also regular as it is a union of regular languages D 533 NFAacceptable Q DFAacceptable In this section we shall prove that the set of NFA acceptable languages is a subset of the DFA acceptable languagesi Since inclusion in the opposite direction is obvious as noted above we have the following theoremi Theorem 17 A language is accepted by an NFA if and only if it is accepted by some DFA 62 CHAPTER 5 FINITE AUTOMATA Figure 58 This is the DFA that is obtained by performing the NFAetorDFA conversion procedure on the NFA shown in Figure 55 Aside from state labels it matches the DFA shown in Figure 54 Consequently the utility of nondeterminism in the context of nite automaton lies in ease of ex pression and greater simplicity not the ability to describe a wider variety of languages That is it is typically much easier to construct an NFA than the corresponding DFA and the resulting machine is frequently much simpler to understand For most theoretical purposes such as proving that languages are DFAacceptable we neednlt ever perform an explicit conversion to a DFA it is sufficient to know that an equivalent DFA existsl Proof We need only show that every NFA can be replaced with a DFA that accepts exactly the same language since the converse is immediate The following algorithm describes the steps for creating the state diagram of an equivalent DFA from the state diagram of an NFAl The sates of the constructed DFA are labeled with the elements of 2Q where Q is the set of states of the NFA That is the new labels are sets of labels that appear in the original NFAl This labeling re ects the fact that with each transition the equivalent DFA simulates progress along multiple paths in the NFA simultaneously This strategy eliminates nondeterminism at the cost of possibly introducing exponentially more states To construct a DFA that is equivalent to a given NFA 1 Create a start state for the DFA and label it with the set of all states in the original NFA that can be reached without moving the read head ie without reading a single symbol This set consists of the NFA s start state and all the states that can be reached from it via null 53 FINITE AUTOMATA AND REGULAR LANGUAGES 63 Figure 59 An example of an NFA with multiple null transitions Such transitions complicate the conversion of the machine to a DFA at each step we must nd all states that are reachable by these transitions as well transitions 2 Expand all edges in the NFA that are labeled with strings that is replace them with a sequence of edges each labeled with single charactersi Give each 0 the new intermediate states a unique labels We shall call this new and equivalent machine the expanded NFAi 3 Loop forever a Let S be a state in the DFA under construction that has no outgoing edge labeled a where a is some symbol in 2 If there is no such state then exit the loops b Let T be the set of all states reachable in the expanded NFA via exactly one atransition in combination with any number of null transitions starting from any of the states 8 6 5 c If a state with the label T does not already exist in the DFA create one Note that T may be the empty set 0 d Add an edge from S to T and label it with the symbol a 4 If the DFA has a state that is labeled 3 add a loop back to itself for each a E 2 That is make it a trap 5 Let A be the set of all states in the DFA whose labels contain one or more accept states of the original NFAi Let A be the set of accept states of the DFAi By applying this algorithm to the previous NFA which accepted the language ab Uac we arrive at the DFA shown in Figure 58 Note that step number 1 above did not apply here since every edge in the original NFA was labeled by a single symbols Coincidentally the resulting DFA is identical to the one in Figure 54 except for the state labelsi This will not always be the cases Frequently the above algorithm will introduce far more states than are necessary and be more complex than a machine built directly from the language descriptions The purpose of this conversion algorithm is primarily 39 it simply t t the A 39 of NFAs and DFAsi As a nal example consider the NFA shown in Figure 59 which has three null transitionsi Note in particular that two additional states are now reachable from the start state via null transitions 64 CHAPTER 5 FINITE AUTOMATA Figure 510 This is the machine obtained by converting the NFA shown in Figure 59 to a DFA Note that all null transitions are gone and all missing transitions have been lled in so they are included in the start of the constructed DFAi Converting this NFA to a DFA7 we arrive at the machine shown in Figure 510 In nding the three state labels along the top it was necessary to follow multiple null transitions in the original NFAi 534 Correctness of the NFA Conversion Algorithm In the previous section we showed that the class of NFAacceptable languages was a subset of the DFAacceptable languages by giving a conversion algorithm from NFAs to equivalent DFAsi Well now show that the DFA constructed by the algorithm in fact recognize the same language as the original NFAi Theorem 18 Let M Q7 740141 A be an arbitrary nondeterministie nite automaton NFA 53 FINITE AUTOMATA AND REGULAR LANGUAGES 65 and let M Q 2 q6A6 be a deterministic nite automaton DEA where Q SMw l w E 2 510 2 E 511 16 sue 512 A SMwle2 SMw A9 0 5 13 6 SMuaSMualu 2 a62 514 Then M and M are equivalent in that they accept the same language Proof We rst verify that the DEA de ned in Theorem 18 is properly formedl Recall that SM denotes the set of states that machine M can reach by reading string w which is a singleton set for a deterministic machine So by Equation 510 each element of Q is a subset of Thus Q is nite since Q Q 2Q and Q is nite It is also easy to check that A Q Q ql E Q and that 6 is a total function that is 6 Q X 2 A Q is singlevalued and de ned over all of Q X 2quot We now show that M To do this we rst prove that SMw SMw Vw E 2l 515 That is after reading the string w the deterministic machine M is left in the state with label SM w which is the set of states in M that are reachable by reading the string w This is easily established by induction on the length of wl As the base case when 0 or w 5 note that SMYQE qt3 by the de nition of a DEA 5 16 SM 5 l by Equation 512 517 As the inductive hypothesis assume that SMyw SM for all w E 2 with S no Now let w ua where u E 2 n and a E 2 Let L be the state that M is left in after reading the string u that is SMyu Then SMua 6 qa by the de nition of a DEA 6 SM u a by the inductive hypothesis SM ua l by Equation 514 Thus Equation 5 15 holds by induction Finally we show that w E M ltgt w E M by a sequence of double implications w E M ltgt SMw N A Z by the de nition of M ltgt SMw E A by Equation 513 ltgt SMyw N A Z by Equation 515 ltgt w E M l by the de nition of M Consequently M M which demonstrates that M and M are equivalent Theorem 19 The algorithm described earlier for converting an NFA to an equivalent DFA con structs the machine de ned in Theorem 18 Proof To be supplied D 66 CHAPTER 5 FINITE AUTOMATA 54 Closure Properties of Regular Languages By their very de nition the set of regular languages over a common alphabet are closed with respect to concatenation union and Kleene stari In this section we extend this list to include several more common operations on languages Theorem 20 Regular languages are closed under 1 39 it t t 39 and symmetric dz erence Proof First we shall use the fact that every regular language is accepted by some DFA to prove that regular languages are closed under complementationi et e a regular language and let M Q 2 go A 6 be a DFA that accepts it Now de ne another DFA M E Q go Q 7 146 We claim that M accepts the language 2 7 L which is the complement L of the language L This is easy to see since SMyw SM for every w E 2 so SMyw g Q 7 A if and only if SM 6 Al Therefore M rejects a string w if and only if M accepts it Given the closure properties we have established thus far the remaining operations are easily seen to be closed We need only observe that each can be expressed in terms of other operations under which regular languages have been previously shown to be closed Thus LmL2 EUE 5 18 L17L2 wEL1 w L2 LmE 5 19 LleLQ weLluLglngl Lg L17L2UL27L1i 520 The operation denoted by 9 is known as symmetn39c di cerence It is important to observe that the method we used above to construct a DFA that accepts L from one that accepts L does not carry over directly to NFAsi That is if we simply change accepting states into nonaccepting states and vise versa in an arbitrary NFA the resulting machine will in general not accept the complement of the original language 55 The Pumping Lemma We start by establishing several elementary rules governing the operation of nite automata that will prove useful lateri Let E be an alphabet and let a and 1 denote arbitrary symbols in 2 From the de nition of the yields relation for the nite automaton M denoted by b we may obtain the elementary composition rule 417a b 4275 gt 417 F 427107 521 which simply af rms that the next step taken by machine M is unaffected by the symbol immediately following the current position of the read headi From the de nition of the relation P rule 521 may be inductively extended to strings yielding the rule 4w 9728 qhuv 42 52 55 THE PUMPING LEMMA 67 i where u and 1 now denote strings in 2 By the transitivity of b we may then immediately formulate the fundamental composition rule for nite automata 41 b 4275 A 4271 b 4375 gt 417 b 4375 523 From rule 523 it follows by induction on n that w t w e M t 45 524 for all n E N Finally from rules 523 and 524 together we obtain 41 b 4275 A 4271 b 4275 gt 417111 b 4275 525 for all n E N When ql is the initial state of machine M rule 525 may be be more succinctly stated as SMu SMuv gt SMu SMuvn 526 for all n E N Rule 526 will be an essential element in establishing the rst pumping lemma which is a powerful tool for identifying languages that cannot be recognized by nite automatai This lemma is proven in the following section While it is easy to see from a counting argument that there are uncountably many nonregular iiei nonDFAacceptable languages such an argument provides no means of identifying a speci c nonregular languagei To prove that a language is not regular we must show that no DFA recognizes it As is frequently the case a negative result eg that no DFA accepts language L is more challenging to prove than the corresponding positive result eg that machine M accepts language L since the latter can be demonstrated by simply exhibiting a machine that accepts L To attack this problem we rst introduce the notion of a pumping property that may or may not be possessed by any given string in a language De nition 15 Let h be a natural number and let L be a language Then we shall say that w E L has the rst pumping property of length h with respect to the language L if and only if there exist strings I y and 2 not necessarily in the language L such that w zyz S h 2 l and zynz E L for all n 2 0 The word pumping in this de nition is motivated by the fact that any number of copies of the string y may be inserted or pumped into the machine M following the pre x 1 without changing the state of Mr The following powerful lemma provides a method for demonstrating nonregularity of a large class of but not all of the nonregular languagesi Lemma 1 The Pumping Lemma for Regular Languages Let L be a regular language Then for some h E N every w E L with 2 h has the rst pumping property of length 16 68 CHAPTER 5 FINITE AUTOMATA Proof Let L be a regular language and let M E Qq0 A 6 be a DFA that recognizes L that is L Let Z and let w be any string in L with k where k 2 Z If no such string exists then the theorem holds trivially so let us assume that such a string does exist De ne the function fw 012Hik A Q by fw 4 such that SM Here wij denotes the substring l when i S j and 5 when i gt ji More formally we may de ne wi j inductively by deg wli Owli17jl ifi Si wz J 5 ifigtj Thus fw is the state of machine M after reading the rst 239 symbols of the string wi Since M is deterministic there is exactly one such state As special cases note that 16100 go where go is the initial state and fw k E A since w E L by de nition Now observe that 012mk k1gt Ql because w was chosen so that k 2 Therefore by the pigeonhole principle it follows that fw cannot be injectivei From this we may conclude that there exist distinct integers i andj such that 0 S i lt j S k and fw fw We now claim that the substrings z y and 2 given by z wli y wli17jl 2 wlj17kl satisfy all the criteria necessary to show that w has the pumping property of length kl Obviously w zyz j S k and j 7i gt 0 by the very de nition of the substringsi Moreover since SM fw fw SM my it follows from Equation 526 that SM SM for all n E N and consequently SM SM for all n E N Since w E L it follows that SM SM Moreover since SM N A f 0 where A is the set of accept states in M it follows that zynz E L for all n 2 0 We have thus shown that for any w E L with 2 E where Z is the number of states in same machine that accepts L the string w must have the pumping property of length 16 which proves the lemma D Observe that lemma 1 is useful in showing that some languages are not regular but it is of no use in showing that a given language is regular That is the pumping property77 is a necessary but not a su cient condition for a language to be regular 551 Predicate and Contrapositive Form To actually apply the lemma 1 we will need to change into its contrapositive formi To simplify this manipulation it will be convenient to introduce some new predicate notation The rst such predicate is Haw 5 27 55 THE PUMPING LEMMA 69 which is a predicate on strings w which is de ned to be true if and only if w has the rst pumping property of length It with respect to the language L Note that the predicate depends on both the length It and the language L which we make explicit by af xing k and L as subscript and superscript respectivelyi Next let Reg be a predicate on languages such that RegL is true if and only if L is regular We may now state the rst pumping lemma more succinctly in terms of these predicatesi Lemma 2 Predicate form of Lemma 1 Let L be any language Then RegL 3k 6 N Vw e L lwl 2 k 3 Him 528 Since every element of a regular language must possess the pumping property for suf ciently large k a language that fails to have this property for all It cannot be regular Stated in this way it is clearly the contrapositive of lemma 2 that allows us to draw conclusions about a language Thus we state the contrapositive as a lemma in its own right Lemma 3 Contrapositive of Lemma 2 Let L be any language Then We 6 N 3w 6 L lwl 2 k ning RegLi 529 The bracketed expression in Equation 529 is the negation of the bracketed expression in Equa tion 528 To make use of lemma 3 we must show that the negation of the predicate Hg holds for some suf ciently long string w 6 L We now look at what is entailed by this negationi To make the notation a bit more concise welll encapsulate various properties as predicates on strings or languagesi First we de ne the partition and the pump predicates by Pkwzyz if w zyz S k 2 l 530 de QLzy 2 Vn E N zynz E L 531 respectively where k E N Note that equations Equation 5 30 and 531 actually de ne families of predicatesi The predicate Pk w z y 2 is true if and only if the strings I y an 2 orm a partition of the string w that satis es all of the languageindependent6 prerequisites of the rst pumping property of length It and QLzyz is true if and only if the remaining languagedependent7 property holdsi We may then de ne the complete pumping property predicate by Kim A 317y72Pkw7I7y72 A QL17972 7 532 which is true if and only if the string w E L possesses the pumping property of length It with respect to the language L as de ned earlieri Recall that z y and 2 may be any strings in 2 and needn t 5Recall that A D B is simply shorthand for AVB Hence the negation of 31 Vy Amy 3 31 y is V1 3yAm yA aBm 6We refer to these properties as languageindependent because they merely require myz to be a proper partition of w with restrictions on the lengths of my and y These properties do not mention the language L at all 7 his predicate is always relative to a speci c language L as it requires all of the pumped strings to be in L Hence we refer to it as languageedependent 70 CHAPTER 5 FINITE AUTOMATA be elements of L themselves We now have H w 31yzPkwzyz QLzyz Vzyz Pkwzyz V QLzyz Vzy2Pkwzyz D QLzyz Vzy2Pkwzyz D 3n zy 26L 2Pkwzyz 3 3n WWII My We now assemble the various pieces and state the nal predicate form of the pumping lemma for regular languages as another lemmai Lemma 4 Contrapositive of Lemma 2 Version 2 Let L be any language If Vh E N 3w 6 L 2 k Vzy2Pkwzyz 3 3n zynz L l 533 then L is not regular Thus to show that a language L is not not regular using the contrapositive of the rst pumping lemma we must show that for every k E N we can nd some string w E L with 2 k that fails to have the pumping property of length hi That is for all valid partitionings of w into zyz meaning w zyz S h and 2 1 there is some n E N such that zynz L We now show how to apply this lemmai 552 Applying the Pumping Lemma Theorem 21 The language L1 anbn l n 2 l is not regular Proof Let k E N be given We shall now select a string w 6 L1 that is of length at least k since we are at liberty to chose any such w welll choose one that will make the rest of the proof as easy as possible Let w akbk which clearly has length greater than hi Now consider any partition w zyz such that S k and 2 1 Then y must consist entirely of as This is precisely why the string akbk was convenient for this particular proofi This implies that zy22 will have more as than Is More precisely W241 lwla M gt lwlb lylb W245 534 since lyla 2 1 while lylb 0 It follows immediately that zy22 cannot be of the form anb which always has the same number of as a s Consequently my 2 Lli We have thus shown that for any h E N there is a string of length at least k namely akbk that fails to have the pumping property of length hi Therefore L1 is not regular D Theorem 22 The language L2 a l n E N n is prime is not regular 56 SUMMARY 71 Proof Let k E N be given Let w up where p is any prime greater than max2 k Then w 6 L2 with 2 k as required Now suppose that w zyz is any partitioning of w such that 2 1 Then lel mm n 71m 20 n 7 mm where m 2 1 We must now show that for at least one choice of n E N 10 n 7 lm is not prime from which it will follow that zynz has nonprime length and therefore is not in L2 But this is easy to do for if we let n 10 1 then we have lzyp zl 10an pm17 535 which is a composite number since both factors are greater than one Therefore we have thus shown that for any k E N there is a w 6 L2 of length at least k namely up where p 2 max2 k is any prime that fails to have the pumping property of length kl Therefore L2 is not regular D Notice that in the above proof we did not require the partition to have the property that S k as this constraint was of no help whatsoeveri By omitting the constraint we were actually considering a larger class of partitions of w yet even among this larger class none of them possessed the pumping property In general then for the sake of clarity we may omit the constraint if we do not make use of it in any way 553 Limitations of the First Pumping Lemma It is important to remember that there are some nonregular languages that the rst pumping lemma will fail to identify as such For example consider the language L3 cnkanbnlngt0 and 1621 lntuitively this language is not regular since no single nite automaton can ensure that the string of as and the string of bls are of equal length for all n gt 0 for large enough n the machines capacity to coun 77 is exceeded However the First Pumping Lemma cannot demonstrate directly that L3 is not regular To see this note that for any w 6 L3 we can always write w zyz where z 5 y c and 2 is the remainder of the string Then zynz 6 L3 for all n E N Consequently L3 satis es the pumping lemma even though it is not regular 56 Summary Here is a summary of the de nitions and behaviors of both DFAs and NFAsi 57 Exercises 1 De ne a DFA that accepts each of the following languages where the alphabet is assumed to be 2 abi You need only draw the state diagramsi CHAPTER 5 FINITE AUTOMATA Deterministic Finite Automata Initialization o The state of the machine is set to the initial state gel 0 The input string is Written on the semiin nite tape With its rst symbol Writen in the rst cell of the taper All other cells are considered blank 0 The read head is positioned over the rst cell of the tape Which is the rst symbol of the input string Transitions depend on o The current state 0 The symbol under the read headi What happens at each step 0 The control unit advances to one of a nite number of states 0 The read head moves exactly one cell to the right Halts when 0 The read head moves onto a blank cell of the taper Formal De nition of a Deterministic Finite Automaton as a 5 tuple 2Qq0A6 Symbol Name Description lnput alphabet Finite nonempty set for encoding input strings State set Finite nonempty set of state labels lnitial state The machine starts in this special state of Accept states The machine accepts the string if it halts in one of these states A function from Q X 2 to Transition function a All strings in 2 that begin With aa or end With 1212 or both b All strings in 2 c All strings in 2 d All strings in 2 that contain no runs longer than two that do not contain the substring abai With an even number of ds 2 Construct a DFA or NFA that accepts each of the following languages over the alphabet 2 a b c You need only exhibit the state diagrams but indicate Whether it is a DFA or an 5 7 EXERCISES Nondeterministic Finite Automata Initialization o Exactly the same as a DFA Transitions depend on o The current state 0 Zero or more contiguous symbols7 starting With the one under the read head and moving to the right 0 A nondeterministic choice among available alternatives What happens at each step 0 The control unit advances to one of a nite number of states 0 The read head moves zero or more cells to the right Halts when 0 The read head moves onto a blank cell of the tape 0 An unde ned transition is encountered 73 Formal De nition of a Nondeterministic Finite Automaton as a 5 tuple E7Q7q07A7A Symbol Name Description 2 Input alphabet Finite nonempty set for encoding input strings Q State set Finite nonempty set of state labelsi qo lnitial state The machine starts in this special state of lhe machine accepts the string if same sequence of nondetermm A Accept states istic choices allows the machine to halt by reaching the end of the string in one of these states A Transition relation A nite subset of Q X 2 X Q NFA7 and explain Why it is one or the other We shall always regard a machine as a DFA if it ts the more restrictive de nition7 even though every DFA can also be regarded as an NFAi a L1 a 1210 b L2 my w c L3 a 1212quot cch d L4 5Ua2nb2m1in 2 0 and m 2 0 CHAPTER 5 FINITE AUTOMATA e L5 w E 2 l w does not contain two or more contiguous as f L5 w E 2 l w contains no runs of as or bls longer than two g L7 w E 2 l w does not contain all three letters 3 Let M1 and M2 be DFAs that accept the regular languages a 1212quot and aab respectively where the alphabet is 2 ab Use the construction described in section 53 to bui d an NFA that accepts the union of these two languages then convert the NFA to a DFAi Draw all the relevant state diagrams to document the entire process 4 Let M be an NFAi In each case below brie y explain what must be true about the state diagram of M in order for the statement to be true a M is the empty set b M contains the empty string 5 c M is in nite d The yields relation P is a partial function 5 For each of the following languages over the alphabet 2 a 120 either show that it is regular or prove that it is not To show that a language is regular you may either give a regular expression for it or draw a state diagram of a DFA or NFA that accepts it a L1 w E 2 l is a power of2 b L2 w E 2 l is a multiple of 3 c L3 w E 2 l lwla is even and lwlb is odd Ulbl lb l Hint of the two languages L4 and L5 one is regular and the other is not Moreover the one that is regular can be expressed in a much simpler way d L4 uvcl u and v are strings in ab with lulu e L5 ucv l u and v are strings in ab with lulu 6 Given the 5tuple descriptions of two DFAs M1 and M2 over the same alphabet 2 construct a 5tuple for an NFA that a Accepts M1U M2i b Accepts M1 o M2i c Accepts M1 M2i In each case construct the 5tuples of the NFA by performing various set operations on the elements of the 5tuples for M1 and Mg You may assume without loss of generality that the state sets of M1 and M2 are disjoint 7 Consider the following modi cations to the de nition of a DFAi Would these changes affect the class of languages accepted by this type of machine That is would the modi ed class of machines be capable of accepting a larger smaller or the same set of languages Give brief justi cations for your answers a Only one accept state is allowed 57 00 50 H 53 H H H E0 EXERCISES 75 b No selfloops are allowed that is each transition must lead to a state that is distinct rom the current state c No loops of any kind are allowed making the state diagram a directed acyclic graph or Which of your answers change if these same modi cations are applied to the de nition of an NFA Consider the following modi cations to the de nition of an NFA Would these changes affect the class of languages accepted by this type of machine That is would the modi ed class of machines be capable of accepting a larger smaller or the same set of languages Give brief justi cations for your answers a A string is accepted if and only if all possible paths lead to an accept state b Multiple start states are allowed which are selected nondeterministically c At most two transitions are allowed out of each state d All accept states must be terminal that is no transitions are allowed out of an accept state Let M1 and M2 be DFAs that accept the regular languages aaquot and 1212 respectively where the alphabet is ab Build an NFA that accepts the intersection of these two languages by combining M1 and M2 appropriately Show that this machine accepts the null language that is the language containing no strings not even the empty string The machine you will build could be denoted by mum where the bar indicates the machine accepting the complement of the language accepted by the original machine Construct a DEA that recognizes strings in 0 l with the following property Each string when interpreted as a binary number is congruent to 3 modulo 5 That is the remainder is 3 when divided by 5 The binary number should be written in the natural leftto right manner that is with the most signi cant digits appearing rst on the tape Hint if s 6 01 is congruent to k mod 5 when interpreted as a binary number what is the string 81 congruent to How about the string 80 Give an example of a regular language L1 and a nonregular language L2 over the same alphabet such that the concatenation L1 0 L2 is regular Give an example of a language over 2 a b with the following property if all the bls are removed from every string the resulting language over 2 a is not regular but if all the bls are replaced with as then the resulting language is regular over 2 Let L be any language over the alphabet E and de ne LP to be the set of pre xes of strings in L That is def LP 1062lwvuforsomeuELandv E Show that if L is regular then LP is also regular Hint To create a DEA that accepts LP we can start with a DEA that accepts L and change nothing more than the set of accept states

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.