I'm trying to practice for my exams, and the one problem I'm having is creating context grammars for a specific set. I am not sure how to go about creating context grammar, except for the trivial case. Here are some cfg's that I have been practicing on, can you check for correctness, thanks.

S1 = { }

1)

2)

3)

S2 = { } for z = x + y

This one I wasn't sure. This is what I got so far from reduction :

//Substituting x+y for z I got :

S2 = { }

Now I'm not sure where to got with this. A similar problem also exist for condition z = x-y

Any hints and not the answer directly would be very appreciated. Thank you.

EDIT:

So for S2 here is what I got :

S2 = { }

For the case we can express y as y = x + n, n>= 0

Thus we can decompose S2 into:

S2 = { }

S2 = { }

Thus for the above S2 we can now easily make a CFG as so:

Q -> U | null

U -> aUa| T

T -> nTa| S

S -> bSa | null

we can apply similar process for , and I got:

A -> B | null

B -> aBa | C

C -> aCa | D

D -> bDa | null

Thus a grammar that accepts S2 is G ->Q|A

Is that correct?