# Proof that the language is not regular (Pumping Lemma) [closed]

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

• You cannot "assume that he pumping length is three". Your proof has to work for any pumping length. Feb 23, 2018 at 17:06
• How does the input look like? Is it over the alphabet $\{1,0,+\}$? Feb 23, 2018 at 17:06
• 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? Feb 23, 2018 at 20:37
• Please state a question, in the title if possible. Feb 24, 2018 at 20:34
• I think the language is over {0,1} and it consists of the strings {111,10101,1001001,...}, which is clearly not regular Feb 25, 2018 at 10:35