Learning of construction of finite automata from examples using hill-climbing : RR: Regular set Recognizer
Learning of construction of finite automata from examples using hill-climbing : RR: Regular set Recognizer
复制标题
从使用爬山的例子中学习有限自动机的构造：RR：正则集识别器
DOI：
10.21236/ada120123
复制
发表时间：
1982
期刊：
影响因子：
--
通讯作者：
M. Tomita
中科院分区：
文献类型：
--
作者：
M. Tomita
摘要：本文所讨论的问题是有限自动机的启发式引导学习。在给定正样本串和负样本串的情况下，生成有限自动机，并增量地精化以接受所有正样本但不接受负样本。本文描述了应用爬山来修改有限自动机以接受所需的正则语言的一些实验。我们证明了许多问题都可以用这个简单的方法来解决。然后，我们描述了如果正样本和/或负样本稍有改变，而无需从头开始，如何“重建”有限自动机的方法。最后，我们有了一个实际的系统。Regular Set Recognizer：Regular Set Recognizer，它学习从人类老师一个接一个地给出的样本中识别规则集。
Abstract : The problem addressed in this paper is heuristically-guided learning of finite automata from examples. Given positive sample strings and negative sample strings, a finite automaton is generated and incrementally refined to accept all positive samples but do no negative samples. This paper describes some experiments in applying hill-climbing to modify finite automata to accept a desired regular language. We show that many problems can be solved by this simple method. We then describe the method how to 're-construct' a finite automaton if the positive and/or negative samples are slightly altered, without starting from the beginning. Finally, we have an actual system. RR: Regular set Recognizer, that learns to recognize a regular set from the samples that are given by a human teacher one by one.