Language to Generate Powers of 2 Using a Language Containing Decimal Numbers

Question

For this question, I have the alphabet $\Sigma=\{0,1,2,3,4,5,6,7,8,9\}$. I also have the language $L$ over $\Sigma$ described as the language such that the strings $w$ contained in $L$ are powers of 2 and $w$ is treated as a decimal number. I then need to:

1. Design a grammar to generate $L$
2. Classify the grammar (Regular, Context-free, etc.)
3. Show that $L$ is not regular
4. Determine if $L$ is a context-free language (answering only yes or no)

The original question is in the image below, for reference. I'm not entirely sure how to start on this question in particular. Most of the examples I had in my automata class consisted of much smaller alphabets and more precise languages. Any help with an explanation would be much appreciated.

Thank you in advance!

Answer 1

L is not context-free

Periodicity for context-free languages of bounded growth: Let $w_n$ be the number of words of length $n$ in a given regular language. If the sequence $w_1, w_2, \cdots$ is bounded (bounded growth), then it is eventually periodic.

Proof: This follows from the fact that every context-free language of bounded growth is a union of paired loops, which is the theorem 2.1 in the paper On a conjecture about slender context-free languages by Lucian Ilie, 1994.

---

Let $w_n$ be the number of words of length $n$ in $L$. $w_n=\#\{k\in\Bbb N\mid n-1\le k\log_{10}2 \lt n\}$. Since $\log_{10}2$ is irrational, the sequence $w_1, w_2, \cdots$ cannot be eventually periodic. So $L$ is not context-free. Hence, it is not regular, either.

As rici pointed out, it is not difficult to prove that $L$ is not context free by applying the pumping lemma to any word in $L$ that is long enough. The above more conceptual proof is presented in the hope that it might raise more interest and more questions.

$L$ is context-sensitive

According to rici's comment, we can write a context-sensitive grammar which multiplies a decimal number by two. Use marker tokens which move right to left over the number; you'll need two of them because of the possibility of carry. As with many other cases of context-sensitive grammars, the actual construction might be apt to get lengthy and tricky, sometimes even debatable.

Another conceptual way to see $L$ is context-sensitive is using linear bounded automaton (LBA) that accepts a context-sensitive language. It is easy to see that we can divide by 2 repeatedly using a linear bounded automaton. More specifically, we can design a LBA such that given an input of $S m E$, where $m$ is a sequence of decimal digits and where $S$ and $E$ are start marker and end marker respectively, it will output $S1\square\square\cdots\square E$, where $\square$ stands for the special blank symbol if and only if $m$ is the decimal representation of some power of 2.

An exercise

Let language $L_U$ over $\Sigma=\{0,1,2,3,4,5,6,7,8,9\}$ be the language of words which are positive integers whose prime factors belong to a finite set $U$ of prime numbers when they are treated as decimal numbers. Show that $L_U$ is context-sensitive but not context-free.