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 casewe 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?
