What kind of language is $\{\text{bin}(n)\text{oct}(n)^R \colon n \in \mathbb{N} \}$? Regular? Context-free? Neither? Prove.

Question

I need to determine if the $L$ is:

1. regular
2. context free but not regular
3. None of the above

$$ L =\{\text{bin}(n)\text{oct}(n)^R \colon n \in \mathbb{N} \}$$

To do that, I chose this word: $$\text{bin}(2^{3n+3} -1)\text{oct}(8^{n+1} -1)$$

So that this word gives

$$\underbrace{111\ldots111}_{3n+3}\underbrace{777\ldots777}_{n+1}$$

It is easy to pump it out using the pumping theorem for regular languages, thus, $L$ is not regular.

Now, I think that it is not context free. I use the pumping theorem for context free languages on the same word.

Let $n$ be the constant "provided" by the lemma. We have:

$$1^{3n+3}7^{n+1} = uvwxy$$

There are three options:

1. Pumping only applies to ones - remove the selected block and we are done.
2. Pumping only applies to sevens - same as above.
3. We are pumping a block with prefix of ones and suffix of sevens.
   1. More sevens than ones - Remove this block. We are done.
   2. Same number - Remove the block. We are done.
   3. More ones than sevens - three ones and a seven - Now this doesn't work :(

Is there a better word to do the job? If not, is there an easy grammar for this language?

Answer 1

You can use rici's suggestion, but some extra work is needed. Let $C$ be the context-free language defined by the grammar $$ S \to 000S0 + 001S1 + 010S2 + \ldots + 111S7 + \epsilon $$ To obtain your language, you still have to get rid of the words ending with a $0$ or starting with one or two $0$'s. For the first step, take $$ L = \{\epsilon\} \cup \bigl(C \cap \{0, \ldots, 7\}^*\{1, \ldots 7\}\bigr) $$ For the second part, set $A = \{0, \ldots 7\}$ and take $$ \{\epsilon\} \cup \Bigl((L \cap 1A^*) \cup \bigl(0^{-1}(L \cap 01A^*)\bigr) \cup \bigl((00)^{-1}(L \cap 001A^*)\bigr)\Bigr) $$ Since context-free languages are closed under intersection with regular languages and under left quotients with words, the resulting language is context-free.