Operational complexity and right linear grammars

被引:1
|
作者
Dassow, Juergen [1 ]
机构
[1] Otto von Guericke Univ, Fak Informat, PSF 4120, D-39016 Magdeburg, Germany
关键词
Context free languages;
D O I
10.1007/s00236-020-00386-3
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
For a regular language L, let Var(L) be the minimal number of nonterminals necessary to generate L by right linear grammars. Moreover, for natural numbers k(1), k(2), ..., k(n) and an n-ary regularity preserving operation f, let g(f)(Var) (k(1), k(2), ..., k(n)) be the set of all numbers k such that there are regular languages L-1, L-2, ..., L-n such that Var(L-i) = k(i) for 1 <= i <= n and Var(f (L-1, L-2, ..., L-n)) = k. We completely determine the sets g(f)(Var) for the operations reversal, Kleene-closures + and *, and union; and we give partial results for product and intersection.
引用
收藏
页码:281 / 299
页数:19
相关论文
共 50 条