Context free grammar for $L= \{0^i1^ic0^j1^j | j = i+1 \}$

Question

Description

This is an exercise for Formal Language course, I'm asked to find a grammar for language:

$L = \{ 0^i1^ic0^j1^j | j = i+1 \}$

As an example: 01c0011 can be generated using this language, so does 0011c000111.

What I've tried

The difficulty is around the j = i + 1 controlling, I've tried something like this:

S -> 0A11
A -> 0A1 | 1B00
B -> 1B0 | c

Although it can generate all strings that L can generate, but if you take B -> c to terminate the generation early, the string such as "001c00111" doesn't belong to L anymore.

Can somebody give me some advice on this? Better yet, can you tell me what is the correct way to solve such problems? (given language, find CFG)

Answer 1

It is to be expected that you have difficulties finding a context-free grammar since the language is not context-free.

Indeed, suppose it is; it should verify the pumping lemma for context-free languages. Let $n$ be the pumping length and $u = 0^n1^nc0^{n+1}1^{n+1} \in L$. The pumping lemma states that there exists a decomposition $u = vwxyz$ such that:

1. $|wxy| \leqslant n$;
2. $|wy| > 0$;
3. for all $k\geqslant 0$, $vw^kxy^kz\in L$.

Now suppose the first two points are verified. Let us distinguish:

• if $wxy$ is composed of only $0$'s or $1$'s, then $vxz$ does not contain as many $0$'s as $1$'s, so $vxz\notin L$;
• if $w$ or $y$ contains $c$, then $vxz$ does not contain $c$, so $vxz\notin L$;
• if $x$ contains $c$, then $w$ contains only $1$'s and $y$ contains only $0$'s (given $|wxy| \leqslant n$), and $vxz = 0^n1^mc0^k1^{n+1}$, with $m\neq n$ or $k\neq n+1$, so $vxz\notin L$;
• if $w$ or $y$ contains $0$'s AND $1$'s, then $vw^2xy^2z$ contains $010101$ as a subsequence, so $vw^2xy^2z\notin L$;
• given the previous cases, the only possibility is that $wxy$ is a subword of the $0^n1^n$ part or the $0^{n+1}1^{n+1}$ part. Since $wy\neq \varepsilon$, it means that $vxz = 0^i1^jc0^k1^{\ell}$ with either $k \neq i + 1$ or $\ell \neq j + 1$, so $vxz\notin L$.

In each case, we proved that the property 3. cannot be verified. We conclude by contradiction that $L$ is not context-free.

Answer 2

@Nathaniel has actually given a nice proof and standard one. (Wanted to write my answer as comment but having less points.) I would like to conclude with a short point while you continue with your course it'll be helpful.

To identify RL: if language is finite => then it's regular else if its infinite , single alphabet language(unary language) is regular and if it is resulting in an Arithmetic progression kind of string length. And if more than one alphabets are there in the language but aren't dependent on each other , the language is Regular.

To identify CFL , it must be having :

language is regular

or

it's a language in which there's no such comparison with the bottom of the stack,

since comparison is done with the top of the stack in PDA or

there are not more than two dependent alphabets 

 or 
there are not more than two independent alphabets