I am having some problems trying to work out a context-free grammar for the following language:
L = { a^x b^y : y>=x, y-x is odd }
At the moment I have the following, but that does not work completely
S -> aSb | Sb |epsilon
How do I address the y-x is odd aspect of this language? It is the one thing I am unsure how to do.
Starting with your grammar:
S -> aSb | Sb |epsilon
This is going to generate a^x b^y with y >= x. That's pretty close but, as you have noted, fails the "y - x is odd" test.
How can we fix this? Well, if y >= x and y - x is odd, then y = x + z, where z is some positive odd number. What does this mean? It means
that your first production, S -> aSb, is perfectly fine: we need a way to add arbitrarily many a's and keep the number of b's the same.
that your second production, S -> bS, has a big problem: this allows you to add any number of b's, but you have to add an odd number of b's.
that your third production, S -> epsilon, has a big problem: this allows you not to add any more b's, but zero is not an odd number.
To fix this, we can think up a grammar for the language of odd-length strings of b's, and replace the S in the RHS of the production S -> aSb. This will be guaranteed to give you both conditions. A grammar for odd-length strings of b's:
B -> b | bbB
Combining with your grammar and getting rid of the bad productions:
S -> aSb | B
B -> b | bbB
That should do it.