2
$\begingroup$

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 \}$$

The answer i've attempted is:
$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$

$\endgroup$
1
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ for C it would be just C -> pXq $\endgroup$ – James arthur Nov 26 '18 at 16:33
  • $\begingroup$ Correct. Or, in fact, $C->pCq\mid \epsilon$. $\endgroup$ – Apass.Jack Nov 26 '18 at 16:42
  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Nov 26 '18 at 16:42
  • $\begingroup$ I've attempted a final answer and i got: S -> XccY, X -> nXh | nX | ϵ , Y -> n $\endgroup$ – James arthur Nov 26 '18 at 18:33
  • $\begingroup$ 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? $\endgroup$ – Apass.Jack Nov 26 '18 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.