Pumping lemma (Regular language)

5
votes

I need some help with a pumping lemma problem.

L = { {a,b,c}* | #a(L) < #b(L) < #c(L) }

This is what I got so far:

y = uvw is the string from the pumping lemma.

I let y = abbc^n, n is the length from the pumping lemma. y is in L because the number of a:s is less than the number of b:s, and the number of b:s is less than the number of c:s.

I let u = a, v = bb and w = c^n. |uv| < y, as stated in pumping lemma. If I "pump" (bb)^2 then i get

y = abbbbc^n which violates the rule #b(L) < #c(L).

Is this right ? Am I on the "right path" ?

Thanks

1
regular-languageautomataformal-languagespumping-lemma
You are seeking to use the pumping lemma to prove that the language described is regular? Or that it is not regular? Either way, you don't get to choose the substring to repeat: the pumping lemma merely says that there is some n such that in any sentence s of length >= n there is some division of s into uvw such that | uw | < n, | v | >= 1, and u v ^ i w is a sentence for all i. (Since 'c' is always repeatable in this language, you may have a challenge finding sentences in which dividing the sentence on some internal c does not work.) – C. M. Sperberg-McQueen

1 Answers

7
votes

The main idea of the pumping lemma is to tell you that when you have a regular language L with infinite number of terms there is a pattern in the language that repeats forever.

The regular expression associated with that language will contain KLEENE-STAR(pattern).

The automaton associated with that regular expression (and language) will contain a loop.

The proof is done using the pigeon principle.

This image is very suggestive.

Note that all terms must start in q0 and end in qn in this case. So, the automata defining the language is finite (max N states), so there are a limited number of states, but the words (i.e. terms) can have >N letters. The pigeon principle tells us that there must be a state that is reached 2 times, so at that state a loop will be present.

In your notation, you can make the correspondence with the image so:

  • your u is x from image

  • v is y in image

  • w is z from image

To arrive from q0 to qn, you can use any of the strings from the set: { uw , uvw, uvvw, uvvvw, ... }.

In this particular case the pattern P is y, the set X is {xz xyz xyyz xyyyz ...} and S is length(x)+length(y).