It is known that the set of derivation trees of a given CFG constitutes a regular tree-language, where a regular tree-language is a tree-language that can be recognized by a tree automaton [1]}.
Sakakibara has generalized Angluin's \({\textbf {L}^*}\)  algorithm (for learning regular languages using mq and eq) to learning a tree automaton, and provided a polynomial learning algorithm for CFGs using smq and seq [2]}.
Let \(\mathsf {T}(\mathcal {G})\)  denote the set of derivation trees of a CFG \(\mathcal {G}\) , and \(\mathsf {S}(\mathsf {T}(\mathcal {G}))\)  the set of unlabeled derivation trees (namely the structured strings of \(\mathcal {G}\) ).
While a membership query (mq) asks whether a given string \(w\)  is in the unknown grammar \(\mathcal {G}\) ,
a structured membership query (smq) asks whether a structured string \(s\)  is in \(\mathsf {S}(\mathsf {T}(\mathcal {G}))\)  and a structured equivalence query (seq) answers whether the queried CFG \(\mathcal {G}^{\prime }\)  is structurally equivalent to the unknown grammar \(\mathcal {G}\) , and accompanies a negative answer with a structured string \(s^{\prime }\)  in the symmetric difference of \(\mathsf {S}(\mathsf {T}(\mathcal {G}^{\prime }))\)  and \(\mathsf {S}(\mathsf {T}(\mathcal {G}))\) .
