Block-Deterministic Regular Languages
Block-Deterministic Regular Languages
复制标题
DOI：
10.1007/3-540-45446-2_12
复制
发表时间：
2001-10
期刊：
影响因子：
--
通讯作者：
D. Giammarresi;R. Montalbano;D. Wood
中科院分区：
文献类型：
--
作者：
D. Giammarresi;R. Montalbano;D. Wood
我们介绍了阻塞、块标记和块确定性正则表达式的概念。我们用确定性格卢什科夫块自动机来表征块确定性正则表达式。结果可以被视为具有确定性格卢什科夫自动机的一明确正则表达式的表征的概括。此外，当语言 L 具有块确定性表达式 E 时，我们可以为 L 构造一个确定性有限状态自动机，其大小与 E 的大小呈线性关系。
We introduce the notions of blocked, block-marked and block-deterministic regular expressions. We characterize block-deterministic regular expressions with deterministic Glushkov block automata. The results can be viewed as a generalization of the characterization of one-unambiguous regular expressions with deterministic Glushkov automata. In addition, when a language L has a block-deterministic expression E, we can construct a deterministic finite-state automaton forLthat has size linear in the size ofE.