Control sets on grammars

From MaRDI portal





Let \(G\) be a phrase structure grammar and \(C\) a set of sequences of rules of \(G\). \(L_t(G)\) consists of those words generated by leftmost derivations of \(G\) whose corresponding sequence of rules is in \(C\). The following result is typical: Theorem. If \(G\) is an arbitrary phrase structure grammar, \(L_t(G)\) is an abstract family of languages (AFL) if \(C\) is. Corollary. If \(C\) is regular then \(L_t(G)\) is context free. Corollary. For each recursively enumerable set \(R\) there exists a context free grammar \(G\) and a context tree language \(C\) so that \(L_t(G)=R\).




Cited in
(59)








This page was built for publication: Control sets on grammars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5539750)