Pumping lemma Peter Linz examples

Question

Prove language is regular or not using pumping lemma -

1. L={a^nb^l :n!=l}

2. L={(ab)^na^k  : n>k ,k>=0}

Plzz explain using pumping lemma.....

Comments

dont know

---

Why is it that all regular languages can be pumped?

Consider the characterisation of a regular language, as being recognised by some Discrete Finite Automaton, M, with some finite number of states n.

Then, consider some string in the language of M, which we shall call w, for which |w| ≥ n holds true.

In checking w, M must pass through |w| + 1 states (including its start and end states). So, by the pigeonhole principle, M must pass through some states more than once (because |w| + 1 > n).

Let w = a₁a₂...a_n

Imagine these are the state transitions of M, starting at q_s and ending at q_f, in processing w:

  a

₁ a₂ a₃ ... a_n q_s → q₁ → q₂ → ... → q_n = q_f

Now let's look at the section of these state transitions where M repeats a state, we'll call that state R:

  a

₁ a₂ a₃ a_r a_r+1 a_r+2 a_r+k a_r+k+1 a_r+k+2 a_n q_s → q₁ → q₂ → ... → q_r = R → q_r+1 → ... → q_r+k = R → q_r+k+1 → ... → q_n = q_f

Let us use a shorthand here to say this:

  a

₁ a₂ a₃ a_r q_s → q₁ → q₂ → ... → q_r

is the same as this:

   v
q

_s →* q_r

where v = a₁a₂...a_r

Now let us split w into three parts, w = vxu, in the following way:

v = a

₁a₂...a_r x = a_r+1a_r+2...a_r+k u = a_r+k+1a_r+k+2...a_n

Now we see that for v:

   v
q

_s →* R

And for x:

  x
R →* R

And for u:

  u
R →* q

_f

(All I have done is split up the longer state transition diagram above into three separate ones)

Here you see that M will also accept vu, vxxu, vxxxu, ..., vxⁱu for i ≥ 0, because processing the string x at state R, keeps M in state R.

Essentially, the purpose of the pumping lemma is to find that bit of the string that does not alter the state of M when processed.

Now you may wonder. What if there are no strings recognised by M for which |w| ≥ n holds true?

Well, in that case, you can infer that the language is regular, simply by the fact that it is finite (All finite subsets of ∑* are regular), and furthermore, the pumping lemma is vacuously true, you simply choose a pumping length p > n, and you can be sure that all strings recognised by M that also satisfy |w| ≥ p can be pumped (because you know that none exist).

Answer 1

1.

L={a^n b^l / n!=l}

Pumping Leema says if there is a language which can be divided into 3 parts such as xy^iz, then for any value of i this should also be inside language.

here for y there are 3 choices y=a , or y=ab or y=b but in all three cases there is no way to make sure this comparison.

for example if y =a then aaabbb should not be accepted but x=a y^2 =aa and z=bbb

hence pumping leema is failed here!

Comments

That means we can divide in any way we want...or there is some specific rule...

---

For a regular language L, there exists a p > 0 such that for all w ∈ L where |w| ≥ p, there exists some split w = vxu, for which the following holds:

• |vx| ≤ p
• |x| > 0
• vxⁱu ∈ L for all i ≥ 0

---

For a context-free language L, there exists a p > 0 such that for all w ∈ L where |w| ≥ p, there exists some split w = uxyzv for which the following holds:

• |xyz| ≤ p
• |xz| > 0
• uxⁱyzⁱv ∈ L for all i ≥ 0