Consider the following grammar:

<s> ::= <n> <c>
<n> ::= a <n> b | ε
<c> ::= c <c> | ε

Which one of the following statements is true of the parse tree for the string aaabbbcc if <s> is the start symbol of the grammar?

This parse tree contains 8 interior nodes and 10 leaf nodes.
  • This parse tree contains 10 interior nodes and 8 leaf nodes.
  • This parse tree contains 8 interior nodes and 9 leaf nodes.
  • This parse tree does not exist because the string aaabbbcc does not belong to the language generated by this grammar.
  • There is more than one answer because there exist two parse trees for the string aaabbbcc.

Make sure to build the whole parse tree with pencil and paper.

The start symbol of the grammar is the root node of the parse tree.

Each interior node of the parse tree is a non-terminal that appears on the left-hand side of a production.

The number of children of a node is equal to the number of terminals and non-terminals on the right-hand side of the corresponding production.

Remember that each ε in the tree counts as one leaf node, even though ε is not really a terminal (nor a non-terminal).