I need a regular language $ L\subseteq \{0,1\}^{*} $ so that $unary(L)$ is not context free.

unary of $L$ is defined by: $$unary(L) = \{0^{1x} : x \in L \}$$

Example $L = \{0, 11\} $ $\rightarrow unary(L) = \{00, 0000000\}$

Any help would be great.


closed as unclear what you're asking by FrankW, David Richerby, Juho, Raphael Apr 7 '14 at 6:08

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ This is a dump of a problem, not a question. If you have a specific question regarding the wording of the problem or about concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – FrankW Apr 6 '14 at 20:10

Let $L = 10^*$ and observe that $$\text{unary}(L) = \{ 1, 11, 1111, 11111111, \dots\} = \{1^{2^i} \mid i \in \mathbb{N} \}.$$

Can you prove the rest yourself?

  • $\begingroup$ Can you explain how you got unary(L). Because the way I see it $L = \{1, 10, 100, 1000, 1000, ... \}$ so with the above definition $unary(L) = \{0^3, 0^6, 0^{12}, 0^{24}, ... \}$ isn't it? $\endgroup$ – user130554 Apr 6 '14 at 22:08
  • $\begingroup$ I must admit I don't really get your definition of $\text{unary}(L)$, but the point is that you must make a language where the words grow exponentially fast. If the next element in your sequence is $0^{48}$, i.e., your sequence is $3 \cdot 2^i$ you should be fine. $\endgroup$ – Pål GD Apr 6 '14 at 22:23
  • $\begingroup$ The way I understand the definition is that if you have say $L = \{0, 01\}$ you replace $x$ with $0$ and $01$ and when you convert this binary number into a decimal, you get the exponent for $0$, so for example $0^{10}, 0^{101}$ would give $unary(L) = \{0^2 , 0^5 \}$, but I do understand it now. Thanks for your help! $\endgroup$ – user130554 Apr 6 '14 at 22:43
  • 1
    $\begingroup$ Please consider not to encourage undesirable posting behaviour. $\endgroup$ – Raphael Apr 7 '14 at 6:09

Not the answer you're looking for? Browse other questions tagged or ask your own question.