document.write( "Question 1017019: I am at a loss on how to do proofs for this class. Here is the problem:\r
\n" ); document.write( "\n" ); document.write( "Let Σ = { 0, 1, #} and for a string w  {0, 1}*, let bin(w) be the integer that w represents as a binary number. Prove (using the pumping lemma for regular languages) that L = {x # y | x, y  {0, 1}*, and
\n" ); document.write( "y = 0 k , where k = bin(x) } is not regular\r
\n" ); document.write( "\n" ); document.write( "If someone can walk me through the steps, I am willing to hire them via PayPal. Thank you.
\n" ); document.write( " \n" ); document.write( "

Algebra.Com's Answer #633401 by richard1234(7193) $\"\"$ $\"About$

You can put this solution on YOUR website!
I'm a little confused by the role of bin(x). If w = \"100101\" then does bin(w) = 100101? (I would hope bin(w) is not 37 since only 0's and 1's are allowed). If so, what is the purpose of using bin(x)?\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "To prove that L is not regular, assume otherwise that L is regular. By the pumping lemma, there exists a pumping length

such that for every string

s.t.

can be split into three strings

such that:\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "1.

0\">
\n" ); document.write( "2.

\n" ); document.write( "3. For all nonnegative integers i,

\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Note that # must appear in

(if it were in

then by pumping, we would have strings in L with multiple #'s which is not allowed).\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Let

. This has length 2p+2 > p, so the pumping lemma must hold. Because (1)^p has length p, we must have that # is part of s_3, and s_2 is composed of entirely 1's.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "By the pumping lemma, there must exist a nonempty substring

contained in the first (1)^p such that we can duplicate

to produce more words in L. But this leads to contradiction, as such words do not satisfy the requirements of L.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "I haven't worked a whole lot with the pumping lemma before, so if anyone else sees any mistakes (e.g. me misinterpreting bin(x)), feel free to point them out. \n" ); document.write( "

\n" );