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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Further Remarks on Context-Free Grammars with Subregular Control Languages

  • Jürgen Dassow

摘要

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.