1
votes

I'm having some trouble with a rather difficult question. I'm being asked to prove the language {0^n 1^m 0^n | m,n >= 0} is irregular using the pumping lemma. In all the examples I've seen, the language is only being raised to the same variable (i.e. a^n b^n). So my question is, how do I pick a suitable string to test if this language is irregular?

Also a follow up to that question is once I have my string, how do you decompose the string into the form xyz where |xy| <= pumping length and |y| >=1?

1
Perhaps more suited to the Computer Science site?Dour High Arch

1 Answers

0
votes

In the examples you have seen before there were different letters: n as followed by bs. In the given example, the are n Os at the beginning and the end of the word. The language adds 0 or more 1s between those blocks of Os.

W in the pumping lemma is decomposed w = x y z with |xy| <= m and |y| > 0, where m is the pumping length. The way to pick a w is the same as before: you pick it such that the xy is completely inside a block consisting of one letter. For a^n b^n a word in L was selected such that xy would entirely consist of as, such that if it is 'pumped' there will be more as than bs. So you need at least m as and for the word to be in the language that means you need to pick m bs. The shortest is w = a^mb^m. For the new troublesome language, pick a word in this L such that xy consists entirely of Os (in the first block), such that if it is 'pumped' there will be more Os in the first block than the last block -and the number of 1s in the middle was not changed. However, you need to include at least one 1 in your original word otherwise there is only one block of Os - and pumped words in fact are in the language, which means there is no contradiction and thus not proof that L is irregular.