On Regularity of Context-Free Languages
On Regularity of Context-Free Languages
复制标题
论上下文无关语言的正则性
DOI：
10.1016/0304-3975(82)90124-4
复制
发表时间：
1983
期刊：
影响因子：
--
通讯作者：
G. Rozenberg
中科院分区：
文献类型：
--
作者：
A. Ehrenfeucht;D. Haussler;G. Rozenberg
本文考虑上下文无关语言是正则的条件以及强加于生成上下文无关语言的重写系统（的产生）的条件将保证生成的语言是正则的。特别是：1.(1)给出了酉文法产生式的充分必要条件，保证生成的语言是正则的(酉文法是一个半图系统，其中每个产生式的左手都是空词)，2.(2)证明了线性语言的交换性蕴含着它的正则性。为了获得前一个结果，我们根据准序给出了正则语言的 Myhill-Nerode 表征的概括，以及关于 Σ* 上子序列嵌入关系的 Higman 准序结果的概括。在获得后一个结果时，我们引入了周期语言类，并演示了如何使用它们来表征交换正则语言。这里我们还利用了准阶理论。
This paper considers conditions under which a context-free language is regular and conditions which imposed on (productions of) a rewriting system generating a context-free language will guarantee that the generated language is regular. In particular:1.(1) necessary and sufficient conditions on productions of a unitary grammar are given that guarantee the generated language to be regular (a unitary grammar is a semi-Thue system in which the left-hand of each production is the empty word), and2.(2) it is proved that commutativity of a linear language implies its regularity. To obtain the former result, we give a generalization of the Myhill–Nerode characterization of the regular languages in terms of well-quasi orders, along with a generalization of Higman's well-quasi order result concerning the subsequence embedding relation on Σ*. In obtaining the latter results, we introduce the class of periodic languages, and demonstrate how they can be used to characterize the commutative regular languages. Here we also utilize the theory of well-quasi orders.