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\}$$

Improve this question
$\endgroup$
7
  • 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, 2018 at 17:06
  • 2
    $\begingroup$ How does the input look like? Is it over the alphabet $\{1,0,+\}$? $\endgroup$
    – Yuval Filmus
    Feb 23, 2018 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, 2018 at 20:37
  • $\begingroup$ Please state a question, in the title if possible. $\endgroup$
    – reinierpost
    Feb 24, 2018 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, 2018 at 10:35

0

Reset to default

Browse other questions tagged or ask your own question.