6
$\begingroup$

In an exercise, I am asked to find a context free grammar for language $L = \{a^{2^k}, k \in \mathbb{N}\}$.

I have been trying to use a "doubling" variable. If $a^{2n} \in L, n\in\mathbb{N}$ then use this variable to double the $a$'s that have been produced by the other language rules.

Is this thinking valid? So far I haven't been able to get anywhere with it, but it seems logical given the double-stack of powers.

$\endgroup$
11
$\begingroup$

$L = \{a^{2^k}, k \in \mathbb{N}\}$ is not a context-free language according to Pumping lemma for context-free languages.

Suppose $L$ is context-free. The pumping lemma says there exists some integer $p \ge 1$ such that every string $s$ in $L$ where $|s| \ge p$ can be written as $s=uvwxy$ where $|vwx|\le p$, $|vx|\ge 1$ and $uv^nwx^ny$ is in $L$ for all $n \ge 0$.

Let $s$ be a string in $L$ longer than $p$, and $u$, $v$, $w$, $x$, and $y$ have the properties given by the pumping lemma. Thus $uwy, uvwxy, uv^2wx^2y\in L$. Let $a$ and $b$ be such that $$|uwy|=2^a, |uvwxy|=2^b$$ Note $b>a$. Then $$|uv^2wx^2y|=2|uvwxy|-|uwy| = 2^{b+1}-2^a = 2^a(2^{b+1-a}-1)$$ But $2^a(2^{b+1-a}-1)$ is not a power of 2, and so $uv^2wx^2y\notin L$.

$\endgroup$
  • 1
    $\begingroup$ This is part of an exercise, therefore highly unlikely that it would ask of a context free grammar on context free Language. Maybe I'm translating it incorrectly? The exercise asks for a "grammar without restrictions (rewrite system)", which I assumed is a context-free grammar. $\endgroup$ – Dimitris Sfounis Sep 13 '15 at 20:27
  • 3
    $\begingroup$ @DimitrisSfounis No context-free grammar exists for non context free language. By "grammar without restrictions" you mean unrestricted grammar? That's grammar for recursively enumerable language, know n as type-0 languages. $\endgroup$ – Terence Hang Sep 13 '15 at 23:14
  • 4
    $\begingroup$ To add to what's been said, an unrestricted grammar for your language is a fairly common example. Do a little bit of digging and it'll turn up. $\endgroup$ – Rick Decker Sep 13 '15 at 23:16
10
$\begingroup$

Your approach does not work: you can't force all the variables to "double" at once using only context-free rules.

As the other answers show, your effort is futile: $L$ is not context-free, so there can be no such grammar.

For reference, context-sensitive rules allow you to control the "doubling". Idea: move markers through the sentence; only with the marker can doubling rules be applied. A second marker triggers termination.

Try for yourself to translate this idea into a grammar!


No luck? here goes:

$\qquad\begin{align*} S &\to \$ A \$ \\ \$ A &\to \$ \bullet A \mid \circ A \\[1ex] \bullet A &\to AA \bullet \\ \bullet \$ &\to \$ \\[1ex] \circ A &\to a \circ \\ \circ \$ &\to \varepsilon\end{align*}$

Note:

  • The first rule sets up end markers.
  • The second rule(s) spawn the two markers; only one $\circ$ can be spawned!
  • Markers can only move to the right, and are absorbed by the last end marker.
  • Markers can not overtake each other.

I'll leave a formal proof of correctness as an exercise; see here for some ideas.

Hint: Each marker is a "phase"; you have $k-1$ $\bullet$-phases that generate $A^{2^k}$, then a single $\circ$-phase that translates all $a$ into $A$.

$\endgroup$
5
$\begingroup$

A language which is a subset of $a^*$ is known as a unary language. There is a complete classification of unary languages which are context-free. In particular, if $L$ is a unary language then the following are equivalent:

  1. $L$ is context-free.

  2. $L$ is regular.

  3. There exists $m$ such that $a^n \in L$ iff $a^{n+m} \in L$.

  4. There exist $m_1,m_2$ and subsets $S_1 \subseteq [m_1],S_2 \subseteq [m_2]$ such that $a^n \in L$ iff $n \in S_1$ or $n-m_1-rm_2 \in S_2$ for some integer $r \geq 0$.

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .