# How to produce a context free grammar for this language?

I've already attempted it but I am finding it difficult to understand if this is correct.

give a context free grammar for the following:

$$\{p^{3m+n}q^nr^2p^m\mid m,n\ge 0 \}$$

$$S \to XY$$
$$X \to pppXp \mid \ q$$
$$Y \to qYr \mid \epsilon$$

I've been trying to understand if i need to break down: $$\{p^{3+m+n} \}$$ in to

$$\{p^{3}p^m p^n \}$$

to give me: pppXp

then q and r would value to

qYr | $$\epsilon$$

A common approach to figure out a context-free grammar for some simple languages is to find, by peeling off terminals, smaller and smaller languages that are nicely structured such that if you use a nonterminal to represent each smaller language, you can restore the larger languages from the smaller ones with a production rule.

$$S=\{p^{3m+n}q^nr^2p^m\mid m,n\ge 0 \}$$

If you peel off $$p^3$$ from the front and $$p$$ from the back $$m$$ times, you got language $$B=\{p^nq^nr^2\mid n\ge 0 \}$$. Can you see how to produce $$S$$ from $$B$$ by one production rule? In fact, that is part of what you have written.

Peeling off $$r^2$$ at the end, you get language $$C=\{p^nq^n\mid n\ge 0 \}$$. Can you get $$B$$ from $$C$$? Can you produce/recall a context-free grammar for $$C$$?

• for C it would be just C -> pXq – James arthur Nov 26 '18 at 16:33
• Correct. Or, in fact, $C->pCq\mid \epsilon$. – Apass.Jack Nov 26 '18 at 16:42
• Just in case you are not aware, as the asker, you can accept an answer if it helps and if you want to say thanks. – Apass.Jack Nov 26 '18 at 16:42
• I've attempted a final answer and i got: S -> XccY, X -> nXh | nX | ϵ , Y -> n – James arthur Nov 26 '18 at 18:33
• The answer to your original image should look like $S\to nAn$, $A\to Bc$, $B\to nBh$. Can you see the peeling off at each level? – Apass.Jack Nov 26 '18 at 19:01