Is $L = \{0^{i}1^{i}0^{j}1^{i} | i, j > 0\}$ a context free language?

206 Views Asked by At

Is the following argument correct?

$L = (A \circ B) \cap C$

where,
$A = \{0^{i}1^{i}$ $|$ $i > 0\}$
$B = \{0^{j}1^{i}$ $|$ $i, j > 0\}$
$C = \{0^{i}1^{j}0^{k}1^{i}$ $|$ $i, j, k > 0\}$

We know that A and B are context free languages and C is also a context free language for which the grammar is as follows.

$S \rightarrow 0S1$ $|$ $1A0$
$A \rightarrow 1A$ $|$ $A0$ $|$ $\epsilon$

Hence, $L$ is a context-free language.

1

There are 1 best solutions below

1
On BEST ANSWER

Your argument does not work, since context-free languages are not closed under intersection. In fact, the linked article uses $\{a^nb^nc^n: n\in \Bbb N\}$ as a model counterexample, which is somewhat similar to your example.

I would recommend a different approach, either trying to directly build a grammar recognizing this language if you think it is context-free, or considering the pumping lemma if you think it is not context-free.