I have to write a grammar for the following language: $$\{1^{n^2} \mid n\geq 1 \}$$ I am having trouble figuring out the production rules. I was thinking of using the fact that $n^2$ can be written as the sum of first $n$ odd numbers but couldn't proceed any further.

  • 3
    $\begingroup$ Your language is not context-free. What kind of grammar are you interested in? A context-sensitive grammar? $\endgroup$ – Yuval Filmus Feb 23 '16 at 16:05
  • 2
    $\begingroup$ The following paper gives a context-sensitive grammar for $\{0^{F_n} : n \geq 0\}$, where $F_n$ is the $n$th Fibonacci paper: fq.math.ca/Scanned/31-1/mootha.pdf. Perhaps this is useful for you. $\endgroup$ – Yuval Filmus Feb 23 '16 at 16:08
  • 2
    $\begingroup$ Context-free-grammar is out of question. As Yuval mentions you can write a context-sensitive grammar. First try to construct an LBA. That will help in understanding how you can go about writing CSG. $\endgroup$ – Shreesh Feb 23 '16 at 16:11
  • $\begingroup$ Any kind of grammar would work but if a context-sensitive is possible, I would like that! I am looking at the paper. :) $\endgroup$ – Pranav Arora Feb 23 '16 at 16:19
  • $\begingroup$ @YuvalFilmus: I looked at the paper but its too difficult for me currently. I doubt the above problem requires so many production rules. :/ $\endgroup$ – Pranav Arora Feb 23 '16 at 16:35

Let $B$ stand for the beginning marker, $A$ stands for a single 1 to be added later, $D$'s are copier markers and $E$ be the end marker. $F$, $G$, $I$, $H$ markers are used to properly generate all $A$'s. The following is not the most efficient grammar, but it will do.

Context free grammar rules:

$S \rightarrow BAFUE\ |\ \epsilon$
$U \rightarrow UD \ | \ D$

Non-contracting grammar rules:

$FD \rightarrow DG$
$AD \rightarrow D1A$
$1D \rightarrow D1$
$A1 \rightarrow 1A$
$BD \rightarrow BH$
$H1 \rightarrow 1H$
$HA\rightarrow AI$
$IA\rightarrow AI$
$IG \rightarrow AAF$

Now some non non-contracting rules:

$FE \rightarrow E$
$B \rightarrow \epsilon$
$AE \rightarrow E$
$E \rightarrow \epsilon$

Though this grammar has four non non-contracting rules, I have left them as it is, to help understanding. With a little effort we can convert it into a non-contracting grammar and then to a context-sensitive-grammar.

$IG \rightarrow AAF$ is the important rule, every time it adds two extra $AA$'s to be later substituted by 1's.

  • $\begingroup$ I was not looking for most efficient grammar rules. I was interested in how we can use simple copy grammars and the fact that $n^2 = 1 + 3 + 5 ...$ to get a (sufficiently) easy grammar. $\endgroup$ – Shreesh Jan 1 '17 at 13:50
  • $\begingroup$ I used non non-contracting to emphasize that what we really want are non-contracting rules and these rules are anomaly. $\endgroup$ – Shreesh Jan 4 '17 at 16:35

Imagine a head that walks over the sentential form and expands some non-terminals it finds. What should the head do?

Start with a single $A$ and the head to the left of it, i.e. $\circ A$. The head passed from left to right and expands every $A$ it finds to a $1$ and a new $A$ -- and the last $A$ spawns a a new $A$ and triggers that the head copies the last block of $1$s.

How do you move the head?

With rules of the form $\circ A \to A \circ$.

How do you control what the head does where?

Introduce marked copies of symbols. For instance, the last $A$ could be a $\hat A$.


Your Answer

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

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