Question

please do B) for me

a. Give the definition of a rightmost derivation of a context free grammar G b. Show that any string that can be generated by any context free grammer G can be generated by a rightmost derivation in that grammer G.

Answer 1

b. In rightmost derivation,  we always expand the rightmost non-terminal first.

Now suppose a string has been generated by some context-free grammar, then that string must have a parse tree which will produce the string from the starting non-terminal S by applying a series of productions.

Now to produce the same string by using rightmost derivation, we can simply follow the production rule in the parse tree in following way :-

1. Start from the root node of parse tree( non-terminal S) and follow the production in the depth first search manner with rightmost non-terminal in the production tree is selected as the next node to explore in depth first search.

2. If we follow the production in depth first search manner with rightmost non-terminal in the children node is selected as the next node to explore in the parse tree then node that the sequence of production rule explored by depth first search in this manner is rightmost derivation method in which we expand the right-most non-terminal first and this will generate the same string.

Hence there always exist rightmost derivation for every string in a context - free grammar.

Please comment for any clarification.