need some help with the following question:
I've watched a few youtube tutorials but I'm struggling to convert this specific CFG
0
$\begingroup$
$\endgroup$
-
$\begingroup$ What did you try? Where did you get stuck? Any resource on context-free grammars should explain how to convert to CNF. You say you've already looked at some resources but you don't give any indication of why they didn't help you. What if somebody spends 15 minutes writing an answer for you but you just say, "sorry, I don't understand that either"? $\endgroup$ – David Richerby Nov 7 '17 at 18:31
0
$\begingroup$
$\endgroup$
What you want is to have each production be of one of the forms $A \rightarrow BC$, $A \rightarrow x$ (for a terminal $x$), and $S \rightarrow \epsilon$ (where $S$ is the start symbol). The only productions in that grammar which are not of one of these forms are:
- $\text{S} \rightarrow I \text{ VP PP}$
- $\text{VP} \rightarrow ate \text{ NP}$
- $\text{VP} \rightarrow \text{V}$
Hints: try replacing the second production with an equivalent one of the form $A \rightarrow BC$, and try replacing the third production with one of the form $A \rightarrow x$. For the first one, I suggest creating a non-terminal $\text{X}$ such that $\text{X} \rightarrow I \text{ VP}$, and then rewriting the production as $\text{S} \rightarrow \text{X} \text{ VP}$. This production is in the correct form, but now the one for $\text{X}$ isn't; however, it isn't too much work to fix that one as well.
-
$\begingroup$ I got it eventually, turned out to fairly easy. I ended up doing exactly what you suggested $\endgroup$ – BlackBruceLee Nov 8 '17 at 19:55
