2
$\begingroup$

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. original problem 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!

$\endgroup$
  • $\begingroup$ Could you provide a reference to where you have this question from? $\endgroup$ – AcId Apr 28 '19 at 17:56
  • 1
    $\begingroup$ Probably context sensitive grammar (which lets you do about anything). $\endgroup$ – gnasher729 Apr 28 '19 at 17:57
  • $\begingroup$ I'm not sure if this question is from anywhere in particular, or if the professor wrote it himself. It's from an optional assignment, but I'd like to figure it out. $\endgroup$ – MeaninglessCode Apr 28 '19 at 18:24
  • $\begingroup$ In decimal form it is easy to see if a number is a power of 10. I doubt it helps. $\endgroup$ – gnasher729 Apr 28 '19 at 19:52
  • 2
    $\begingroup$ Here's a clue: 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. The last question should be pretty easy to prove using by pumping $\endgroup$ – rici Apr 28 '19 at 22:17
1
$\begingroup$

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.

| cite | improve this answer | |
$\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.