Context Free Grammar for strings of $z^n$y$x^m$ $w^n$

Question

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!

Answer 1

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:

1. Put a z on the left and w on the right. Repeat as many times as you like (maybe zero) then—
2. Put a y in the middle. Then, next to it—
3. 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:

1. You can represent a grammar for $x^n$ by:
   • X -> xX
   • X -> ε
2. You can represent a grammar for $z^m w^m$ by:
   • Q -> zQw
   • Q -> ε
3. You can represent a grammar for $yx^n$ by:
   • X -> Xx
   • X -> y
4. 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.