Discussion
section notes, April 26
By
Elena Nabieva
Example 1:
Applying the Pumping Lemma for CFL’s:
Let L = anbn+1cn+2
Show that L is non-regular.
Proof:
Let p be the pumping length for L.
Let z = apbp+1cp+2
By the pumping lemma, z can be written as uvwxy, s.t.
|vwx| ≤ p and |vx| ≠ 0.
Therefore, vwx cannot contain a’s and c’s at the same time. We consider both of these cases:
Case 1: vwx does not contain any c’s. Therefore vwx contains some a’s and/or some b’s.
By the pumping lemma, uviwxiz is in L for all i ≥ 0.
Consider z’ = uv2wx2z. Compared to the original string z, one of the following three statements is true of z’:
- the number of a’s in z’ is 2 greater than the number of a’s in z.
OR
- the number of b’s in z’ is 2 greater than the number of b’s in z.
OR
- the number of a’s in z’ is 1 greater than the number of a’s in z, and the number of b’s in z’ is 1 greater than the number of b’s in z.
In all three cases, z’ is no longer in the language since z’ no longer
satisfies the following statement, true of all strings in L:
# of a’s < # of b’s < # of c’s.
Therefore, z’ is not in L, in violation of the pumping lemma. Our initial assumption that L is CF leads to a contradiction.
Case 2 - vwx does not contain any a’s - is handled in a similar manner. We can pump down, causing the relationship
# of a’s < # of b’s < # of c’s.
to hold no longer, or can pump up, and increasing either the difference between the number of a’s and b’s or the number of a’s and c’s (or both) to increase beyond what is required by language L.
Note:
In some circumstances, it may be possible to avoid needing
to go through such cases by coming up with some necessary condition for
membership in the language and showing that applying the pumping lemma to a
candidate string results in a string that no longer satisfies the
condition.
For example, consider L = anb2ncn.
Observe that any string w in L satisfies the following equation:
#a’s = #c’s = ¼ * |w|.
Then, if we apply the pumping lemma to string apb2pcp, p being the pumping length, we can go through the two cases as above, observing that in each case, the resulting string no longer satisfies the condition above.
Example 2:
Decision procedure for determining whether or not a regular language is infinite.
Lemma:
Let M be a DFA with n states.
L(M) is infinite iff M accepts some string of length k, n ≤ k < 2n.
Proof:
"if"
Let w be an element of L(M) and n ≤ |w| < 2n. Then we can apply the pumping lemma to produce an infinite number of strings xyiz (w = xyz), for i = 0, 1,...
"only if"
Proof by contradiction. Assume L(M) is infinite but does not contain any string w s.t. n ≤ |w| < 2n. Note that since L(M) is infinite, there is no upper bound on the length of strings in L(M).
Consider the set L' = { w in L(M) : |w| ≥ 2n).
Note that by our assumption, L' = { w in L(M) : |w|
≥>=
n }.
Let be some string z in L' that is as short as any other string in L' (i.e., z has the minimal length ≥ 2n of strings in L(M)).
Since |z| ≥ n, we can apply the Pumping Lemma to z.
z = abc, where |ab| ≤ n and abic is in L(M) for all i.
Consider ab0c = ac. Since |z| ≥ 2n and |b| ≤ n, |ac| ≥ n.
So ac is in L'! But |ac| < |z| (since |b| ≠ 0), which violates the minimality of the length of z.
So we have a contradiction, and our assumption is false.
This proves the Lemma.
Now, we can have the following decision procedure for determining the finiteness of a language L:
Construct a DFA for L. let n = number of states of that DFA.
Run the DFA on all strings over the alphabet of length [n, 2n). Since this set of strings is finite, our procedure will terminate eventually. If the DFA accepts any string from the set, halt and say "yes, the language is infinite."
If the DFA accepts no strings from the set, say "no, the language is
finite."