12

I have troubles in solving/proving this problem. Any ideas please?

Mat
  • 195,986
  • 40
  • 382
  • 396
Jerald James Capao
  • 155
  • 1
  • 1
  • 6

1 Answers1

17

L = {an bm | n > m} is not regular language.

Yes, the problem is tricky at first few try and deserve vote-up.

Pumping Lemma a necessary property of regular language is tool for formal proof that language is not regular language.

Formal definition: Pumping lemma for regular languages

Let L be a regular language. Then there exists an integer p ≥ 1 depending only on L such that every string w in L of length at least p (p is called the "pumping length") can be written as w = xyz (i.e., w can be divided into three sub-strings), satisfying the following conditions:

  1. |y| ≥ 1
  2. |xy| ≤ p
  3. for all i ≥ 0, xyiz ∈ L

Suppose, if you choose string W = an bm where (n + m) ≥ p and n > m + 1. Choice of W is valid but this choice you are not able to show that language is not regular language. Because with this W you always have at-least one choice of y=a to pump new strings in language by repeating a for all values of i (for i =0 and i > 1).

Before I writing my solution to proof the language is not regular. Please understand following points and notice: I made bold every string w and all i in formal definition of pumping lemma above.

  • Although with Some Sufficiently large W in language you are able to generate new string in Language but NOT possible WITH ALL! There are many possible choices for W(below in my proof) with that you can't find any choice of y to generate new string in language for all i >=0. So because every Sufficiently large W not able to generate new string in language hence language is NOT regular.

read: what pumping lemma formal definition says

Proof: using pumping lemma

Step (1): Choose string W = an bm where (n + m) ≥ p and n = m + 1.

Is this choice of W is valid according to pumping lemma?

Yes, such W is in language because number of a = n > number of b =m . W is in language and sufficiently large >= p.

Step (2): Now chose a y to generate new string for all i >= 0.

And no choice is possible for y this time! Why?

First, it is essay to understand that we can't have b symbol in y because it will either generate new strings out of pattern or in resultant string total number of b will be more than total number of a symbols.

Second, we can't chose y = some a's because with i=0 you would get a new string in which number of a s will be less then number b s that is not possible in language.(remember number of a in W was just one more then b so removing any a means in resultant string N(a)=N(b) that is not acceptable because n>m)

So in we could find some W those are sufficiently large but using that we can't generate new string in language that contradict with pumping lemma property of regular language hence then language {an bm | n > m} is not a regular language indeed.

Community
  • 1
  • 1
Grijesh Chauhan
  • 55,177
  • 19
  • 133
  • 197
  • @NavneetSwaminath [believes there is an error](http://stackoverflow.com/a/28617879/2778484) in your post. – chappjc Feb 19 '15 at 22:06
  • Important to note that if even one string of length ≥ p has one value of i ≥ 0 such that x(y^i)z ∉ L then the language is not regular. Took me a minute to realize that. – koziez Feb 27 '15 at 08:40
  • @Grijesh Chauhan , why can't we chooses y=ab inbetween ? Now if we pump y then we get equal number of a's and b's – Zephyr Sep 06 '17 at 19:20
  • 1
    @Zephyr if you choose `y = ab` and repeats `y` for `i` times it will give you pattern like `ababababab.....` for `i` times that would be out of language. This is what I mentioned in *First,* point that "we can not choose symbol `b` in `y` that cause strings out of pattern" – Grijesh Chauhan Sep 07 '17 at 06:33
  • Ohh. Didn't notice that. Thanks for replying. – Zephyr Sep 07 '17 at 07:05
  • @Grijesh Chauhan Sir, can you please me in applying pumping lemma to this language ? https://math.stackexchange.com/questions/2420659/is-the-language-context-free/2420678#2420678. – Zephyr Sep 08 '17 at 06:43
  • @Zephyr try to find all possible values for `y` and repeat that, ask that question on https://cs.stackexchange.com – Grijesh Chauhan Sep 08 '17 at 07:24
  • @Grijesh Chauhan, I think pumping lemma for CFL is slightly different. We pump out 2 variables and divide the string into 5 parts . Can you please look at my explanation in comment and tell me where am I wrong ? Actually now I think that the language is CFL as we can ignore all a's and b's in the string and just compare the number of zeroes and ones which can be easily done using dcfl :O – Zephyr Sep 08 '17 at 12:40