Context Free Grammar for strings of $z^n$y$x^m$ $w^n$ I am trying to make a context-free grammar that generates all the strings in the language:
$\{z^nyx^mw^n : m,n \ge 0\}$.
Right now for my rules I have:
$S\to yX$
$S\to y$
$X\to e$
$X\to xX$
$S\to zXSw$
However, it seems to generate some incorrect strings, for example:
S->zXSw->zxXSw->zxxXSw->zxxSw->zxxzXSw->zxxzyw
Does anyone know how I could fix these rules to construct the correct context-free grammar? Any help or tips would be appreciated, thank you!
 A: You have a great start. I think you can consolidate the special cases for "y". In general, I like to think of the nonterminal symbols as stages of a process. In this case, we can assemble the string using the following process:

*

*Put a z on the left and w on the right. Repeat as many times as you like (maybe zero) then—

*Put a y in the middle. Then, next to it—

*Put an x on the right. Repeat as many times as you like (possibly zero).

That's basically what you have; all you might want to do is add a separate nonterminal to represent the adding a y stage. So:

*

*S -> zSw

*S -> yX

*X -> xX

*X-> ε


Another way to assemble these grammars is by building them up recursively. You have most of the pieces in place already in your original answer:

*

*You can represent a grammar for $x^n$ by:

*

*X -> xX

*X -> ε



*You can represent a grammar for $z^m w^m$ by:

*

*Q -> zQw

*Q -> ε



*You can represent a grammar for $yx^n$ by:

*

*X -> Xx

*X -> y



*You can represent a grammar for $z^maw^m$ by:

*

*Q -> zQw

*Q -> a



So by putting these last two grammars together, you can get the grammar for your language, which is $z^m$ (... )$w^m$ with $yx^n$ in the middle:

*

*S -> zSw

*S -> X

*X -> Xx

*X -> y

This grammar also does the job well.
