The Grammatical Inference Problem for the Szilard Languages of Linear Grammars
The Grammatical Inference Problem for the Szilard Languages of Linear Grammars
复制标题
线性语法的Szilard语言的语法推理问题
DOI：
10.1016/0020-0190(90)90074-8
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
E. Mäkinen
中科院分区：
文献类型：
--
作者：
E. Mäkinen
传统的语法推理问题是确定一个语法G，生成由样本定义的语言。最近（见例[8，9，12]），人们对推断所讨论的文法的结构也越来越感兴趣，即在生成L（G）的许多文法中，我们希望有一个具有某种特定派生结构的文法。在文献[8，9，12]中，文法的结构是用派生树来描述的。描述文法结构的另一种方法是使用Szilard语言。一个文法的西拉德语言根据文法的产生式为每一个终止派生包含一个词。上下文无关文法的Szilard语言一般是非上下文无关的，但是每个线性文法的Szilard语言是正则的[5-71]。除了上下文无关文法的（一般的）Szilard语言之外，我们还可以定义与最左或最右导子相关的Szilard语言。这些语言总是确定性上下文无关语言[5，7]。本文讨论线性文法的Szilard语言。在这种情况下，（一般）西拉德语言与西拉德语言的最左和最右派生词相一致。我们表明，推理问题的结构相关的线性文法可以解决一个概念上简单的算法在线性时间。我们的方法使得有可能减少的问题推断的上下文无关语法的结构回到正常的语法推理问题。我们提出的算法也是感兴趣的语法推理的一般理论。也就是说，线性文法的Szilard语言类是零可逆语言的一个真子类。Angluin [1]提出了一个从正样本中推断零可逆正则语言的有效算法。Angluin算法的时间复杂度取决于集合并问题的时间复杂度。除了我们的算法在概念上比Angluin的算法更简单之外，它的渐近速度也更快。
The traditional grammatical inference problem is to identify a grammar G that generates the language defined by the samples. Recently (see eg [8, 9, 12]), there has been an increased interest in inferring also the structure of the grammars in question, ie, among the many grammars generating L (G) we desire the one having some specific derivational structure. In [8, 9, 12] the structure of grammars is described by using derivation trees. Another method for describing the structure of a grammar is to use Szilard languages. The Szilard language of a grammar contains a word for every terminating derivation according to the productions of the grammar. The Szilard language of a context-free grammar is in general non-contextfree, but the Szilard language of each linear grammar is regular [5-71. Besides the (general) Szilard language of a context-free grammar, we can define Szilard languages related to the leftmost or rightmost derivations. These languages are always deterministic context-free languages [5, 7]. In this paper we deal with the Szilard languages of linear grammars. In this case the (general) Szilard language coincides the Szilard languages related to the leftmost and rightmost derivations. We show that the inference problem related to the structure of linear grammars can be solved by a conceptually simple algorithm in linear time. Our approach makes it possible to reduce the problem of inferring the structure of a context-free grammar back to the normal grammatical inference problem. The algorithm we present is also of interest for the general theory of grammatical inference. Namely, the class of Szilard languages of linear grammars is a proper subclass of zero-reversible languages. Angluin [l] has presented an efficient algorithm to infer zero-reversible regular languages from positive samples. The time complexity of Angluin’s algorithm is dominated by the time complexity of the set union problem. In addition to the fact that our algorithm is conceptually simpler than Angluin’s algorithm, it is asymptotically faster.