# Math Help - Need to practice CFG

1. ## Need to practice CFG

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 = { $a^xb^y$}

1) $x = y : S->aSb | \epsilon$
2) $x > y : S->aSB | aS | a$
3) $x = 2y: S->aaSy | \epsilon$

S2 = { $a^xb^ya^z$} 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 = { $a^xb^ya^xa^y$}

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 = { $a^xb^ya^xa^y$}

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

Thus we can decompose S2 into:

S2 = { $a^xb^ya^xa^y$}
S2 = { $a^xb^nb^xa^xa^na^x$}

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 $j<=x$, 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?

2. Sorry for the bump, I just was hoping someone can check my work.