How to design a Context-Free Grammar and Pushdown Automaton for the following language:

Question

1. How would you design a context-free grammar for the following language?

$\{p^n \ r^m \ p \ \ b^{m+n} \ \ r^2 ∣ m,n\geq 0\}$

2. Derive a Pushdown Automaton that accepts the same language as the CFG.

Any help given would be greatly appreciated as I am completely lost and struggling to get to grips with CFGs.

Answer 1

Here's a grammar. Terminals are lowercase. Nonterminals are uppercase. The starting symbol is $F.$

$F=Gr^2$

$G = pGb | H$

$H = rHb | p$

Answer 2

A pushdown automaton is a a finite state machine with a stack. So can you design an algorithm where the only memory is the stack?

I would do it as follows. If the first character is not a $p$, reject the string. Otherwise, begin pushing the $p$'s onto the stack. Once you read in an $r$, transition the state and push each $r$ onto the stack. Once you finish reading in the $r$'s, reject if the next character is not a $p$. Otherwise, transition states but do not push anything onto the stack. Now if you read in a non-$b$ character, reject. Otherwise, for each $b$, pop a single character from the stack. After reading in all the $b$'s, the stack should be empty. If it is not, reject the string. Otherwise, transition to the next state. Accept iff you read in two consecutive $r$'s and that is the end of the string.