Search code examples
automatacomputationpumping-lemma

Pumping Lemma Assistance

I recently had an assignment where I was asked to use pumping lemma to show that a language was not regular, and unfortunately got the wrong answer.

The language to prove is non-regular is as follows: L = {ai bj ck: i = j or j = k}

The definition of a pumping lemma that I was given is as follows:

  1. opponent picks m
  2. I want to pick w to contradict the pumping lemma. Use m to pick a string w ∈ L where |w| ≥ m
  3. opponent picks a decomposition of w subject to constraints.
  4. I try to pick an i so that the pumped string wi ∉ L. If found, L is not regular

This subject has proven to be very difficult for me to understand and I feel like a complete airhead because of it, so a detailed explanation as to how I would properly apply a pumping lemma would be appreciated.

Solution

  • Intuitively, the pumping lemma says that long enough words (the length depends only on the language L) in a regular language L must contain a section (of length > 0) which can be repeated as often as desired. Repeating that section ('pumping' the original word) any number of time results in some longer words which are also in the language L.

    The minimal length for the word is the m in the first step of the above definition; the number of times the section is repeated is the i in the 4th step of the above definition.

    The pumping lemma is usually used to show that a language L is not regular. It is a proof by contradiction: assume that L is regular and thus the pumping lemma for regular languages is true for L. Then pick a word w which is in L of sufficient length* and show that regardless of how it is decomposed* some pumped word is not in the language. This contradicts the pumping lemma - which we know to be true. Thus our assumption that the language is regular was wrong and thus the language is not regular. The parts marked with an * cannot be chosen to make things easy - that's why in steps 1 and 3 the 'opponent' selects them.

    The word w is rewritten as w = x y z, where | y | > 0 and |x y| <= m. Both x and z may be of length 0.

    The usual approach is to pick xy to be a string consisting of the same letter such that having more of that same letter (after the pumping) leads to a word not in L.

    No restrictions are specified for the i or the k in the language L in the post, so assuming that i = 0 is allowed, a suitable word might be b^m c^m (that is m bs followed by m cs). Now whatever decomposition the opponent might select, the y will always consist of some bs. Repeating those bs leads to a word with more bs than cs and no as, and thus i != j and j!= k and the word is not in the language.