Further Remarks on Context-Free Grammars with Subregular Control Languages
摘要
A context-free grammar with appearance checking and control language is a triple (G, F, R), where \(G=(N,T,P,S)\) is a context-free grammar, F is a subset of P, and the control language R is a subset of \(P^*\) . The language generated by (G, F, R) consists of all terminal words z with a derivation \(S\mathop {\Longrightarrow}\limits ^{ac}_{q} z\) where q is a word of R and ac means that non-applicable rules can be skipped (without changing the sentential form), if they belong to F. It is known that, by the use of regular control languages, all recursively enumerable languages can be obtained. We prove that this statement also holds, if we use star-free, ordered, regular suffix-closed, union-free, and strictly locally (k)-testable language (where \(k\ge 2\) ). On the other hand, if we restrict to combinational, definite, reverse definite, generalized definite, nilpotent, monoidal, or strictly locally 1-testable languages as control languages, then only context-free languages can be generated.