3

I just started reading about the pumping lemma and know how to perform a few proofs, mostly by contradiction. It is only this particular question which I don't seem to find an answer for. I have no idea on how to begin. I can assume that there has to be a pumping length P and that for all w element of L that the LENGTH(w) >= P. And of course that we can write w as xyz with the three normal conditions of the pumping lemma.

I have to proof that the following language is non regular:

L = {x + y = z | x,y,z element of {0,1}* and #(x) + #(y) = #(z) }

Can someone help me on this, I really want to master the process in proofing these kind of questions?

Edit:
Sorry, forgot to say that the alphabet is {0,1,+,=} and # means the binary value of the string. Like #(00101) = 5 and #(110) = 6.

Alan Moore
  • 73,866
  • 12
  • 100
  • 156
n00b1990
  • 1,189
  • 5
  • 17
  • 25
  • A couple questions for clarification: Are "+" and "=" part of L's alphabet rather than performing mathematical calculation? Does #(x) mean binary value of x? – DPenner1 Mar 14 '13 at 14:33
  • Sorry, I forgot to say what the alphabet is and what the # actually means. I just edited the question. – n00b1990 Mar 14 '13 at 15:18
  • @n00b1990 This language not even Context Free Languages(CFL) [**Read my this answer**](http://stackoverflow.com/questions/13904309/verifier-of-addition-not-regular-but-is-it-context-free?answertab=votes#tab-top) Let me know if you need more help on this. – Grijesh Chauhan Mar 15 '13 at 15:51
  • @n00b1990 I forgot to say in the linked question you can find proof for regular language – Grijesh Chauhan Mar 15 '13 at 16:07
  • @n00b1990 *I can assume that there has to be a pumping length P and that for all w element of L that the `LENGTH(w) >= P`* but **Why?** read [**one**](http://stackoverflow.com/questions/11832371/to-make-sure-pumping-lemma-for-infinite-regular-languages-only/13539823#13539823) and [**two**](http://stackoverflow.com/questions/14705091/pumping-lemma-for-regular-language?answertab=oldest#tab-top) – Grijesh Chauhan Mar 15 '13 at 17:04
  • @ GrijeshChauhan, Sorry, I meant that if you want to proof with the pumping lemma that a language is not regular, you proof it by contradiction. I should've written: Assume that the language is regular. Then there has to be a pumping length P and that for all w element of L that the LENGTH(w) >= P. Right? – n00b1990 Mar 16 '13 at 14:50

2 Answers2

2

Since you want to master the process, I'll point out a few things before showing a proof.

  1. The first thing to notice is that the + and the = may only appear once each. So when you write your string w as w = abc, the pumped portion, b, cannot contain + or = otherwise you'd reach a trivial contradiction (I'm not using the more standard w = xyz notation to avoid confusion with L's definition).

  2. Another thing to notice is that normally, you'd pick a specific string w to pump. In this case, it could be easier to pick a class of strings that share a certain property. The pumping lemma only requires you to reach a contratiction using one string, but there's no reason you can't reach a contradiction with multiple strings.

Proof (in a spoiler):

So let w be any string in L such that |w| ≥ P and x, y, z do not contain leading 0's. By the pumping lemma we can write w as w = abc By pumping lemma, we know b is not empty. Since b cannot contain + or =, it is fully contained in either x, y, or z. Pumping w with any i ≠ 1 results in the binary equation no longer holding since exactly one of x, y, z would be a different number (this is why we needed the no leading 0's bit).

DPenner1
  • 10,037
  • 5
  • 31
  • 46
  • Thank you very much for the help. I understand now. Since the equation must not change it means that our assumption about the language being regular is not correct and thus it has to be non regular. I get it now, thank you! Well done with the spoiler :) – n00b1990 Mar 14 '13 at 21:06
  • Although I am very curious. How can you tell when picking a class of strings is easier then one single string? And what would happen if b did contain a `+ or =` ? Wouldn't that be enough to reach a contradiction and thus a proof? – n00b1990 Mar 14 '13 at 21:11
  • As for choosing a class of strings, it was marginally easier for me, because my thought process was: "Now I need to pump b such that the number changes." And `b`'s which always satisfy that are the ones without leading zeroes. So now that I knew that, I really didn't need to find a specific string, that would just be an extra step. However, like @Patrick87 did, picking a specific string is still completely valid, and depending on your thought process, could be easier. – DPenner1 Mar 15 '13 at 01:59
  • If b contained a `+ or =`, then when you pumped the string for i = 2 (or greater), `b` would contain 2 (or more) `+ or =`. Therefore `w` would not be in the language. This isn't enough for a proof though. This is a contradiction in the specific case where `b` has `+ or =`, but the case where `b` does not contain `+ or =` must still be considered. – DPenner1 Mar 15 '13 at 03:10
  • wouldn't you say that because we found a string `abc` with `b` containing a `+` or `=` that the pumping lemma fails? The pumping lemma checks whether the new "pumped" string is in the language as well. Well, as you say, if `b` contained for example a `+` and you pump for some `i greater then 1` then `b` would contain more then one `+`. Hence, we found a string which is not in the language. The pumping lemma says that every pumped string should in the language, so our conclusion is that the language must not be regular. Shouldn't that be enough for a proof? Or am I missing something? – n00b1990 Mar 16 '13 at 14:46
  • Yes, every string pumped must be in the language...the problem is the string is `w`, not `b`. We don't actually know what `b` contains, since the pumping lemma only guarantees the *existence* of a division `w = abc`. We don't know what that division is, so we must consider all possible divisions, and hence all possible `b`'s. In short, for a single string `w` (or a class like I've done in my proof) you must consider all possible `b`'s. – DPenner1 Mar 16 '13 at 15:44
2

Choose as the string 1(0^n+1) + 1(0^n) = 11(0^n).

In other words, your string will read "the sum of two to the power n+2 plus two to the power n+1 is equal to 11 followed by n zeroes".

Since the string to be pumped will consist entirely of symbols from the first addend, pumping must change the number represented (adding or removing digits to a number will change the number; this is true because our string doesn't contain leading zeroes) and if x + y = z holds, then x' + y = z does not hold if x' != x (over integers, at least).

Since the pumping lemma requires pumped strings to be in the language, and pumping this string fails, we have that the language is not regular.

Patrick87
  • 27,682
  • 3
  • 38
  • 73
  • I partly understand your explanation, but can you tell me why the string is necessary? Or is this a class of strings? I appreciate your help – n00b1990 Mar 14 '13 at 21:08
  • @n00b1990 It's a class of strings, in your language, for which the pumping lemma fails. Proofs using the pumping lemma generally go like this: the pumping lemma says all strings of a certain length should be pumpable; here's a string of at least that length; it's not pumpable; the assumption that the language satisfies the pumping lemma is incorrect; the language is not regular. – Patrick87 Mar 14 '13 at 21:17