0
$\begingroup$

Context-free grammar can generate the string a 2 n for n≥0 .

The production rule P is S→SS|a .

The derivations is, for example:

1) S⇒a (this is when n = 0)

2) S⇒SS⇒aa (this is when n = 1)

3) S⇒SS⇒SSSS⇒aaaa (this is when n = 2)

4) S⇒SS⇒SSSS⇒SSSSSSSS⇒aaaaaaaa (this is when n = 3).

Am I right?

Someone told me yes but it takes a very long time for big enough n;

someone told me no - that this grammar actually generates $a^+$ because it can be $S \Rightarrow SS \Rightarrow SSS \Rightarrow aaa$.

So, does this mean context-free grammar cannot generate the string $a^{2^n}$?

Is there exist any other context-free grammars that can generate this language?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Your grammar doesn't generate this language, for example, $S \to SS \implies SSS \implies aSS \implies aaS \implies aaa$, i.e. $a^3$, but $3 \neq 2^n$. $\endgroup$
    – wvxvw
    Oct 5, 2015 at 12:50
  • $\begingroup$ Thank you. I'll edit my question. "Is there exist any other context-free grammars that can generate this language?" $\endgroup$
    – kate
    Oct 5, 2015 at 12:52
  • $\begingroup$ Just as Shaull already answered: no, this language isn't context-free, since if it was context free it had also to be regular, but if you take $2^n-1$ to be the pumping length, then you cannot pump it because it will be too short. $\endgroup$
    – wvxvw
    Oct 5, 2015 at 12:57
  • 1
    $\begingroup$ Our reference questions contain all the things you need. $\endgroup$
    – Raphael ♦
    Oct 5, 2015 at 15:06

2 Answers 2

Reset to default
5
$\begingroup$

It is well known (and not very difficult to prove) that a context-free language over a unary alphabet $\{a\}$ is regular.

Thus, your question is essentially, "is $\{a^{2^n}:n\in \mathbb N\}$ regular?" And the answer to that is no (easy to prove using the pumping lemma).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you for telling me that because I didn't know. After that I searched but I got a bit confused. A paper says that "It is well known that a context-free language defined over a one-letter alphabet is regular. This implies that unary context-free grammars and unary pushdown automata can be transformed into equivalent finite automata." But then you kindly informed me that $a^{2^n}$ is not regular. So not all strings of unary alphabet is regular? It is confusing how a string is belonged to the context-free language while it can be generated by a finite automaton (= regular grammar).. $\endgroup$
    – kate
    Oct 5, 2015 at 12:25
  • $\begingroup$ By the way, I read in a book that $a^{2^n}$ is a context-sensitive language. I tried to generate it with a context-free grammar in the question above. But I guess my grammar is not correct then. I want to know does this mean context-free grammars cannot generate the string $a^{2^n}$, does it only can be generated by a context-sensitive grammar? $\endgroup$
    – kate
    Oct 5, 2015 at 12:33
  • $\begingroup$ A regular language is a set of strings, not a single string. Not all sets of strings are regular. For a unary alphabet, a set is regular iff it is context-free. As for $a^{2^n}$, as the answer says - it cannot be generated by a context-free grammar, or equivalently - by a finite automaton. You can generate it using a context-sensitive grammar, but that's beside the point. $\endgroup$
    – Shaull
    Oct 5, 2015 at 12:53
  • $\begingroup$ Many thanks for your easy-to-understand explanation. $\endgroup$
    – kate
    Oct 5, 2015 at 12:55
  • $\begingroup$ You may want to repost this answer on the duplicate. $\endgroup$
    – Raphael ♦
    Oct 12, 2015 at 6:39
-1
$\begingroup$

I just realize that my question is the duplicate of this question, but I'll try to put additional answer here myself, now knowing that $a^{2^n}$ is a context-sensitive language, not a context-free language.

An example of the production rules to generate $a^{2^n}, n \geq 0$:

$S \rightarrow \lambda |AA$

$A \rightarrow AA$

Until the above part, it's okay with context-free grammar rules (the derivation being beautifully $S \Rightarrow AA \Rightarrow A^{2^2} \Rightarrow A^{2^3} \Rightarrow \dots$), but then how to change the non-terminal symbols $A$ to the terminal symbols $a$ is tricky. We cannot simply apply $A \rightarrow a$ because it can affect the numbers for example $S \Rightarrow AA \Rightarrow aAA \Rightarrow aaa$, which is not $a^{2^n}$.

This is where the context-sensitive grammar rule comes in handy, simply change both $AA$ to terminal symbols thus preserve the number of $a$'s generated as $a^{2^n}$, i.e.

$AA \rightarrow aa$.

The need to apply this rule is why this language is not a context-free language.

Improve this answer
$\endgroup$
2
  • $\begingroup$ $S \Rightarrow AA \Rightarrow^4 AAAAAA \Rightarrow^4 aaaaaa$ -- too bad. You can generate all $a^{2n}$. $\endgroup$
    – Raphael ♦
    Oct 12, 2015 at 6:37
  • $\begingroup$ It's the same problem.. too bad.. Thanks for pointing out. $\endgroup$
    – kate
    Oct 12, 2015 at 6:57

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