SOLUTION: I am at a loss on how to do proofs for this class. Here is the problem: Let Σ = { 0, 1, #} and for a string w  {0, 1}*, let bin(w) be the integer that w represents

Question 1017019: I am at a loss on how to do proofs for this class. Here is the problem:
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
y = 0 k , where k = bin(x) } is not regular
If someone can walk me through the steps, I am willing to hire them via PayPal. Thank you.

Answer by richard1234(7193) (Show Source): 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)?

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:

1.

3. For all nonnegative integers i,

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).

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.

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.

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.
RELATED QUESTIONS
For the following scores, what is Σ(X + 1)? Scores: A.2, b.0, c.4, d.2 I... (answered by Theo)

A circular pool measures 10 feet across. One cubic yard of concrete is to be used to... (answered by ikleyn,htmentor)

I don't understand how you can determine this problem. its a Qualitative graphing... (answered by stanbon)

The questions is Find a basis for the span of the given vectors. [1, -1, 0], [-1, 0,... (answered by jim_thompson5910)

Hi,my name is Natalia. I solved two problems, but I'm not sure that I did it right. I... (answered by venugopalramana)

I was able to solve the problem correctly (I think) but I am at a loss for the rest. I... (answered by stanbon)

I need help with this problem also. Let me know if I am on the right track. Thank you in (answered by edjones)

Problem to solve is: z^1/2 - 4z^1/4 + 4 = 0 so I let u=z^1/4 and I let u^2=z^1/2... (answered by scott8148)

I have tried to figure out how to properly graph this problem however, when I looked at... (answered by Fombitz,algebrapro18)

SOLUTION: I am at a loss on how to do proofs for this class. Here is the problem: Let &#931; = { 0, 1, #} and for a string w &#61646; {0, 1}*, let bin(w) be the integer that w represents

SOLUTION: I am at a loss on how to do proofs for this class. Here is the problem: Let Σ = { 0, 1, #} and for a string w  {0, 1}*, let bin(w) be the integer that w represents