Question

Given a grammar in GNF and a derivable string in the grammar with the length n, any ___________will halt at depth n.

(a) top-down parser

(b) bottom-up parser

(c) multitape turing machine

(d) none of the mentioned

I have been asked this question by my college professor while I was bunking the class.

The query is from CFL- Other Normal Forms in section Properties of Context Free Languages of Automata Theory

Answer 1

The correct option is (a) top-down parser

Easy explanation: Given a grammar in GNF and a derivable string in the grammar with the length n, any top-down parser will halt at depth n. As the parameter ‘depth’ is mentioned, we will use a top-down parser. Example-LL parser.