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. 
2. 
3. For all nonnegative integers i, 
Note that # must appear in  or  (if it were in  then by pumping, we would have strings in L with multiple #'s which is not allowed).
Let ^p) # ^p) . 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.
|
|
|
