4
$\begingroup$

I need to show that

$\qquad \displaystyle S = \{(10^p)^m \mid p \geq 0, m \geq 0\}$

is not a regular language using pumping lemma.

Can I multiply the product of the powers and express it to: $S = \{ 1^m 0^{pm} \mid \dots \}$ and apply the pumping lemma where I pump 1's then say that the language doesn't accept the new string?

$\endgroup$

migrated from stackoverflow.com Aug 14 '12 at 23:03

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ I figured out that the powers do not multiply rather concatinate. So my previous question is invalid. So my new problem is how do I prove it then? $\endgroup$ – thokthak Mar 20 '12 at 5:44
  • $\begingroup$ Please check out our reference question and edit your question accordingly; where are you stuck, specifically? $\endgroup$ – Raphael Aug 14 '12 at 23:39
7
$\begingroup$

You're right, the superscript in this context means concatenation.

To prove a language isn't regular, you use the fact that any regular language can be "pumped". First, find out what "pumping" a word means (I can't do your homework for you), and then show that your language can not be pumped, and thus, can not be regular. Basically you will take a sufficiently long word that belongs to your language, and show that it cannot be broken up and pumped in such a way that it satisfies the pumping lemma.

Note that the converse of the pumping lemma is not always true: that is, if a language does NOT satisfy the pumping lemma, it may still be non-regular. For this reason, the pumping lemma is used to exclude a language from a set of languages, and not to include a language in a set of languages (such as regular). In other words, satisfying the pumping lemma is a necessary, but not sufficient, condition for a language to be regular.

$\endgroup$
  • 2
    $\begingroup$ i think you mean if a language does satisfy the pumping lemma, that does not mean it is regular, but if a language is regular than it can always be pumped. $\endgroup$ – mondaugen Aug 14 '12 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy