1
$\begingroup$

I have to prove that the following language is not regular:

$$\{ x | x = 10^{2n} + 10^n + 1, n ≥ 1\}$$

I am trying to prove it using Pumping Lemma, however, when I expand the expression I have both addition and multiplication.

I assume that the pumping length is three ($p=3$) and I work on the following word of this language:

$$\{ 10^6 + 10^3 + 1\}$$ $$\{ 1000000 + 1000 +1\}$$

|cite|improve this question
$\endgroup$

closed as unclear what you're asking by David Richerby, Evil, Yuval Filmus, Rick Decker, Ran G. Mar 3 '18 at 7:53

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ You cannot "assume that he pumping length is three". Your proof has to work for any pumping length. $\endgroup$ – Yuval Filmus Feb 23 '18 at 17:06
  • 2
    $\begingroup$ How does the input look like? Is it over the alphabet $\{1,0,+\}$? $\endgroup$ – Yuval Filmus Feb 23 '18 at 17:06
  • 1
    $\begingroup$ I don't understand what the language is. What's the alphabet? Is the language literally strings such as "100+10+1", "10000+100+1", "1000000+1000+1", etc? Or is it encodings of the integers of the form $10^{2n}+10^n+1$? If so, in what base? $\endgroup$ – David Richerby Feb 23 '18 at 20:37
  • $\begingroup$ Please state a question, in the title if possible. $\endgroup$ – reinierpost Feb 24 '18 at 20:34
  • $\begingroup$ I think the language is over {0,1} and it consists of the strings {111,10101,1001001,...}, which is clearly not regular $\endgroup$ – Maiaux Feb 25 '18 at 10:35