ISI2013-PCB-CS-4a

Question

Give a context-free grammar $G$ that generates $L = \{0^i1^j0^k \mid i + k = j\}$.
Prove that $L = L(G)$.

Answer 1

$L=\{0^i1^j0^k\mid j=i+k,i,j,k\geq 0\} =\{\epsilon,0110,011100,001110,\ldots\}$

Now, $L=\{0^i1^{i+k}0^k\mid i,k\geq 0\}$

Here, CFG will be:

• $S \rightarrow S_1S_2$
• $S_1 \rightarrow 0S_11\mid\epsilon$
• $S_2 \rightarrow 1S_20\mid\epsilon$

Comments

why did you consider this condition in question i ,j ,k >=0 .it is not given anywhere . you could have considered i ,j ,k >=1 also.

---

 L={0^i 1^i+k 0^k | i,k≥0} and please explain how did you get this from strings 

---

@sekhar turn the grammar to an easier one 0ⁱ1^j0^k  and j=i+k

now 0ⁱ1^i+k1^k

can be written as 0ⁱ1ⁱ1^k0^k

         then  proceed