程序代做CS代考 1.4 – cscodehelp代写

1.4
1.4 NONREGULAR LANGUAGES 77
NONREGULAR LANGUAGES
To understand the power of finite automata, you must also understand their limitations. In this section, we show how to prove that certain languages cannot be recognized by any finite automaton.
Let’stakethelanguageB = ànn n ≥ à . IfweattempttofindaDFA that recognizes B, we discover that the machine seems to need to remember how many às have been seen so far as it reads the input. Because the number of às isn’t limited, the machine will have to keep track of an unlimited number of possibilities. But it cannot do so with any finite number of states.
Next, we present a method for proving that languages such as B are not regu- lar. Doesn’t the argument already given prove nonregularity because the number of às is unlimited? It does not. Just because the language appears to require un- bounded memory doesn’t mean that it is necessarily so. It does happen to be true for the language B; but other languages seem to require an unlimited number of possibilities, yet actually they are regular. For example, consider two languages over the alphabet Σ = à, :
C = w whasanequalnumberofàsands ,and
D = w w has an equal number of occurrences of à and à as substrings à
At first glance, a recognizing machine appears to need to count in each case, and therefore neither language appears to be regular. As expected, C is not regular, but surprisingly D is regular!6 Thus our intuition can sometimes lead us astray, which is why we need mathematical proofs for certainty. In this section, we show how to prove that certain languages are not regular.
THE PUMPING LEMMA FOR REGULAR LANGUAGES
Our technique for proving nonregularity stems from a theorem about regular languages, traditionally called the pumping lemma. This theorem states that all regular languages have a special property. If we can show that a language does not have this property, we are guaranteed that it is not regular. The property states that
6 See Problem 1.48.
Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
all strings in the language can be “pumped” if they are at least as
long as a certain special value, called the pumping length. That means each
such string contains a section that can be repeated any number of times with the
resulting string remaining in the language.

78 CHAPTER 1 / REGULAR LANGUAGES THEOREM 1.70
Recall the notation where s represents the length of string s, yi means that i copies of y are concatenated together, and yà equals ε.
When s is divided into xyz, either x or z may be ε, but condition 2 says that y ̸= ε. Observe that without condition 2 the theorem would be trivially true. Condition 3 states that the pieces x and y together have length at most p. It is an extra technical condition that we occasionally find useful when proving certain languages to be nonregular. See Example 1.74 for an application of condition 3.
PROOF IDEA Let M = Q, Σ, δ, q, F be a DFA that recognizes A. We assign the pumping length p to be the number of states of M . We show that any string s in A of length at least p may be broken into the three pieces xyz, satisfying our three conditions. What if no strings in A are of length at least p? Then our task is even easier because the theorem becomes vacuously true: Obviously the three conditions hold for all strings of length at least p if there aren’t any such strings.
If s in A has length at least p, consider the sequence of states that M goes through when computing with input s. It starts with q the start state, then goes to, say, q3, then, say, q2à, then q9, and so on, until it reaches the end of s in state q3. With s in A, we know that M accepts s, so q3 is an accept state.
If we let n be the length of s, the sequence of states q,q3,q2à,q9,ààà,q3 has lengthn+. Becausenisatleastp,weknowthatn+isgreaterthanp,the number of states of M. Therefore, the sequence must contain a repeated state. This result is an example of the pigeonhole principle, a fancy name for the rather obvious fact that if p pigeons are placed into fewer than p holes, some hole has to have more than one pigeon in it.
The following figure shows the string s and the sequence of states that M goes through when processing s. State q9 is the one that repeats.
FIGURE 1.71
Example showing state q9 repeating when M reads s
We now divide s into the three pieces x, y, and z. Piece x is the part of s appearing before q9, piece y is the part between the two appearances of q9, and
Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
Pumping lemma If A is a regular language, then there is a number p (the pumping length) where if s is any string in A of length at least p, then s may be divided into three pieces, s = xyz, satisfying the following conditions:
1. for each i ≥ à, xyiz ∈ A, * 1 single s
2. y  à, and * every division s = xyz possibilities
3. xy ≤p.
* at least one condition is not satisfied