<p>Your grammar actually generates the language $a^+$. For instance, since $S \to SS$, one gets $SS \to SSS$ and hence $S \to SS \to SSS \to aaa$. </p>

CC BY-SA 3.0
2015-10-04T23:18:22.943Z
2015-10-04T23:18:22.943Z
J.-E. Pin
<p>Context-free grammar can generate the string $a^{2^n}$ for $n \geq 0$.</p>

<p>The production rule P is $S \rightarrow SS | a$.</p>

<p>The derivations is, for example:</p>

<p>1) $S \Rightarrow a$ (this is when n = 0)</p>

<p>2) $S \Rightarrow SS \Rightarrow aa$ (this is when n = 1)</p>

<p>3) $S \Rightarrow SS \Rightarrow SS SS \Rightarrow aaaa$ (this is when n = 2)</p>

<p>4) $S \Rightarrow SS \Rightarrow SS SS \Rightarrow SS SS SS SS \Rightarrow aaaa aaaa$ (this is when n = 3).</p>

<p>Am I right?</p>

CC BY-SA 3.0
2015-10-04T22:52:19.080Z
Yup :) Though it will eventually take an exponentially long amount of steps to achieve it for high enough $n$'s. (In fact it takes $a^{2^n}-1$ steps starting with $S$ to get to $a^{2^n}$)
Phylliida
<context-free>
Can context-free grammar generates $a^{2^n}$
Kate
# Can context-free grammar generates $a^{2^n}$

(Asked by: username_0 on 2015-10-04)

Context-free grammar can generate the string $a^{2^n}$ for $n \geq 0$.

The production rule P is $S \rightarrow SS | a$.

The derivations is, for example:

1) $S \Rightarrow a$ (this is when n = 0)

2) $S \Rightarrow SS \Rightarrow aa$ (this is when n = 1)

3) $S \Rightarrow SS \Rightarrow SS SS \Rightarrow aaaa$ (this is when n = 2)

4) $S \Rightarrow SS \Rightarrow SS SS \Rightarrow SS SS SS SS \Rightarrow aaaa aaaa$ (this is when n = 3).

Am I right?

**Tags:** context-free
> **Comments:**
> **username_1**: Yup :) Though it will eventually take an exponentially long amount of steps to achieve it for high enough $n$'s. (In fact it takes $a^{2^n}-1$ steps starting with $S$ to get to $a^{2^n}$)  

---

## 1 answers

### Answer by username_2 on 2015-10-04. Score: 3

Your grammar actually generates the language $a^+$. For instance, since $S \to SS$, one gets $SS \to SSS$ and hence $S \to SS \to SSS \to aaa$.


---

