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?

Improve this question
$\endgroup$
2
  • $\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
    Commented Mar 20, 2012 at 5:44
  • $\begingroup$ Please check out our reference question and edit your question accordingly; where are you stuck, specifically? $\endgroup$
    – Raphael
    Commented Aug 14, 2012 at 23:39

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Aug 14, 2012 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.