Grammatical inference consists in learning a formal grammar as a finite state machine or as a set of rewrite rules. In this paper, we are concerned with inferring Nondeterministic Finite Automata (NFA) that must accept some words, and reject some other words from a given sample. This problem can naturally be modeled in SAT. The standard model being enormous, some models based on prefixes, suffixes, and hybrids were designed to generate smaller SAT instances. There is a very simple and obvious property that says: if there is an NFA of size k for a given sample, there is also an NFA of size k+1. We first strengthen this property by adding some characteristics to the NFA of size k+1. Hence, we can use this property to tighten the bounds of the size of the minimal NFA for a given sample. We then propose simplified and refined models for NFA of size k+1 that are smaller than the initial models for NFA of size k. We also propose a reduction algorithm to build an NFA of size k from a specific NFA of size k+1. Finally, we validate our proposition with some experimentation that shows the efficiency of our approach.
翻译:语法推论包括学习正式语法语法,作为有限的国家机器或一套重写规则。在本文中,我们担心的是推断非确定性非非非非非非非非非非非非自制自动规则(NFA)必须接受某些单词,并从某个特定样本中拒绝某些其他词。这个问题自然可以在SAT中模拟。标准模型非常庞大,有些基于前缀、后缀和混合体的模型旨在产生较小的SAT实例。有一个非常简单和明显的属性,它说:如果某个样本有K大小的NFA,那么还有一个k+1大小的NFA(NFA),我们首先通过在K+1大小的NFA中添加一些特性来加强这一属性。因此,我们可以使用这个属性来收紧某个特定样本的最低非常规NFA的尺寸的界限。我们然后提出K+1尺寸的简化和精细型NFAFA的模型,该尺寸小于K级的初始模型。我们还提议用缩算法从一个特定的K+1级的NFA法中建立一定的大小的KFA。</s>