given a binary number b, is there any grammar that generates the languages of $1^x$ where $x$ is $b$ in base $n$ ($n \in \mathbb{N}$) e.g. if $b$ is 1100, the grammar should generates $11,1^{12},1^{36},\cdots$. is there any idea that helps to create the proper grammar?

  • 1
    $\begingroup$ Grammars don't have input. Perhaps you could repeat the exact question you were asked? $\endgroup$ – Yuval Filmus Jan 29 '17 at 22:06
  • $\begingroup$ consider the grammar for a fixed binary number. $\endgroup$ – hamid Jan 29 '17 at 22:24
  • 1
    $\begingroup$ I don't understand your output format, but it seems that your language is finite. $\endgroup$ – Yuval Filmus Jan 29 '17 at 22:26
  • $\begingroup$ No, Since the set of natural numbers are infinite, this language is infinite too. The language L represented above is L = {1^x | x = n^3+n^2+1, n\in N}. Is it not clear? It's my first question here. $\endgroup$ – hamid Jan 29 '17 at 22:35
  • 1
    $\begingroup$ This shouldn't be a comment, but rather part of the question. Nobody should need to read the comments in order to understand the question. $\endgroup$ – Yuval Filmus Jan 29 '17 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.