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$

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.