We introduce NL~*, a learning algorithm for inferring non-deterministic finite-state automata using membership and equivalence queries. More specifically, residual finite-state automata (RFSA) are learned similarly as in Angluin's popular L~* algorithm, which, however, learns deterministic finite-state automata (DFA). Like in a DFA, the states of an RFSA represent residual languages. Unlike a DFA, an RFSA restricts to prime residual languages, which cannot be described as the union of other residual languages. In doing so, RFSA can be exponentially more succinct than DFA. They are, therefore, the preferable choice for many learning applications. The implementation of our algorithm is applied to a collection of examples and confirms the expected advantage of NL~* over L~*.
展开▼
机译：我们介绍NL〜*，一种用于使用成员资格和等价查询推断非确定性有限状态自动机的学习算法。更具体地说，在Angluin的流行L〜*算法中类似地学习剩余有限状态自动机（RFSA），但是，从中学习确定性有限状态自动机（DFA）。喜欢在DFA中，RFSA的状态代表剩余语言。与DFA不同，RFSA限制了素剩余语言，不能被描述为其他剩余语言的联合。在这样做时，RFSA可以比DFA更加简洁。因此，它们是许多学习应用的优选选择。我们的算法的实现应用于示例的集合，并确认NL〜* OVER L〜*的预期优势。
展开▼
