Prove that $L=\{0^n1^{n+1}\ |\ \exists k\in \mathbb{N} :\ 4n+2=6k \}$ is CFL

Question

I've faced a question in my homework, I was able to solve it but not as desired.

Question: Given the language $L=\{0^n1^{n+1}\ |\ \exists k\in \mathbb{N} :\ 4n+2=6k \}$, Prove that it's a CFL (Note: it can be solved without using CFG or PDA).

My Answer: I provided the CFG: $$S\rightarrow 0T11\\T\rightarrow 000T111\ |\ \varepsilon$$

Explanation: The reason I did this that as I see the language consists of the words $(011,000011111,000000011111111,\dots)$ meaning that $(\#_0\ mod\ 3=1 \ and\ \#_1=\#_0+1)$.

I think my solution is true but still, I'm curious how can I solve it without using CFG or CFL, I tend to think that it can be done by using closure properties of CFLs along with pre-learned CFLs.

Note: I've learned that the below language is CFL: $$\{0^n1^n\ :\ n\in \mathbb{N} \}$$ I don't know if it really helps.

If anyone can provide a solution even though using CFLs that he isn't sure I learned or not, I'll be thankful.

Answer 1

The data given in your question are perfectly enough to construct the required solution.

The main observation is that we must start from the known CFL-s and use the closures to obtain the given $L$. So, we start from $\{0^n 1^n\,|\,n\in\mathbb{N}\}$ with no restriction on $n$. Then we use the intersection with a regular language, that can be easily constructed by you given your observation on the constraint $4n + 2 = 6k$. And finally, we concatenate the result with the other regular language (which is also, of course, CFL), namely, $\{1\}$. As a result, we obtain your language $L$. QED

The opposite direction does not work, though. If we take the language $L$ and concatenate it with the language, i.e. $1^*$, we will obtain the regular language, but that proves nothing about the initial language $L$. The simple example is the language $L' = \{ww\,|\,w\in\{a,b\}^+\}$ concatenated with $L''=\{a,b\}^*$ on both sides. Every word in the alphabet $\{a,b\}$ of length no less than 4 contains a square subword (a subword of the form $ww$), thus the language $L'' L' L''$ is regular. But the initial language $L'$ is not even context-free.

Thus, the reasoning works in the direction "given a known CFL, construct the target language using closures", not vice versa.

Answer 2

The language $L_1 = \{0^n1u\mid \exists k: 4n+2=6k, u\in \{0,1\}^*\}$ is regular. There exists a DFA with 4 states recognizing it (proof left to you).

As you have stated, the language $L_2 = \{0^n1^n\mid n\geqslant 0\}$ is CFL.

Then $L = L_1\cap L_2\{1\}$ is an intersection of a regular language and a CFL, hence is CFL.