1
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I understood the solution but still, I couldn't figure out what is the regular language that we have to make an intersection with $\{0^n1^n\ |\ n\in \mathbb{N} \}$. $\endgroup$
    – Mohamad S.
    Mar 26, 2022 at 14:06
  • $\begingroup$ Nathaniel gave you a hint. Besides, you almost had the right construction of the language in your language description preceding the context-free grammar you constructed. $\endgroup$
    – Tonita
    Mar 26, 2022 at 15:59
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ First of all thanks a lot. Also, I wonder how $L_1$ can be built with DFA of 4 states, I think it's not true or you meant NFA. The minimum DFA that I figured out consists of 5 states and I constructed also NFA of 4 states. Here is a picture for them: ibb.co/7pLzXXV $\endgroup$
    – Mohamad S.
    Mar 26, 2022 at 17:24
  • 1
    $\begingroup$ The trap state is assumed as default (and not counted as a "true" state) in some DFA interpretations. $\endgroup$
    – Tonita
    Mar 26, 2022 at 17:25
  • $\begingroup$ @Tonita ah ok thanks. $\endgroup$
    – Mohamad S.
    Mar 26, 2022 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.