# Math Help - Check this Grammer Please

1. ## Check this Grammer Please

The Question :
Prove that the following languages are context-free by giving grammars that accept them.

S = { $0^i 1^j 2^k 3^l$ | i=k and j=l }

I felt like I could just substitute i = k and j = l, int the expression thus having to show that $0^k 1^l 2^k 3^l$ has some CFG.

Is that enough? This is the result I got from doing that :

Let T=
A→1S2 | ϵ
B→0B3 | A |ϵ
Then the CFG that accepts S is T.

2. What you have written does not make much sense to me. Can you show, for example, how you would generate 02 with your grammar ?

3. Oops sorry about that. There was some typo. This is the grammar that I am proposing :

S → B | ϵ
A→1A2 | ϵ
B→0B3 | A |ϵ

So for example it could generate :

B => 0B3 => 00B33 => 00A33 => 001A233 => 001233

4. That grammar is for $0^k1^l2^l3^k$

EDIT: Have you tried showing that the language is not context-free ?

5. I feel so stupid, this is the grammar its supposed to generate $\{ 0^i1^j2^k3^\ell \mid \text{i = \ell and j = k}\}$

6. so i'm guessing it accepts the above set

7. Yes, it does. How far did you proceed with i=k and j=l ?

8. Truthfully, I didn't bother because I am trying to get this homework completed. But I did try it a little, and it seems as
if there is no CFG that recognizes that set. But thats just an intuition. I will try this for practice later, I guess. Thanks again.