本发明涉及主动自动机学习和nfa转换为dfa的技术，具体是一种基于l*算法(lstar算法简称l*算法)将nfa转换为dfa的方法。
背景技术：
1、nfa和dfa是自动机理论中的两种常见模型，在描述和识别语言方面发挥着重要作用。nfa具有较强的表达能力，能够描述一些复杂的语言，由于nfa非确定性的特性，状态转移不唯一，这使得nfa在实际应用中难以直接实现和处理。相比之下，dfa具有确定性转移的特性，更易于实现和处理，适用于许多实际应用中对高效识别特定语言的需求。
2、在实际应用中，尤其是在编译器设计和词法分析等领域，采用将nfa转换为dfa可以有效地优化语言识别过程，这个转换过程可以大大减少自动机的状态数量，降低对内存和计算资源的需求，提高识别的效率，因此，将nfa转换为dfa成为优化语言识别过程的重要步骤。
3、cassandras和lafortune在《introduction to discrete event systems》一书中提出了将nfa转换为dfa的方法，为后续研究奠定了基础。这种方法的核心思想是通过状态子集的构造来表示nfa的状态转移，通过系统地处理状态合并、ε转移等细节，进一步优化了nfa到dfa的转换过程，提高了自动机的识别效率和性能。这些方法的发展丰富了自动机理论，并在编译原理、计算机科学等领域产生了广泛的应用和影响。
4、l*算法最初由angluin在1987年提出，该算法最初用于对一个未知正则集进行建模，l*算法的主要目标是从未知正则集中学习一个等价的有限状态机。通过向oracle(一个对未知正则集的特定查询接口)提出问题，l*算法逐步构建和精炼有限状态机的模型，以使限状态机的模型与未知正则集语言等价，至今为止l*已由最初的针对确定性系统的建模，发展到对于一个非确定系统进行建模，但对非确定系统建模的结果仍是一个非确定性有限状态自动机，对于直接将非确定性系统建模成一个确定性有限状态自动机方面，目前相关的研究较少。
技术实现思路
1、本发明的目的是针对现有技术在转换较大较复杂的nfa时出现的状态爆炸问题和对于部分nfa无法直接转换到最小状态的问题，提供一种基于l*算法将nfa转换为dfa的方法，这种方法将nfa作为被学习目标，不断提出查询、完善观察表，然后构建假设，生成反例不断更新假设，最终学习到与nfa语言等价的dfa模型，这种方法在保证了转换后的模型的状态最小化，为nfa转换为dfa提供了一种新的思路和方法。
2、实现本发明目的的技术方案是：
3、一种基于l*算法将nfa转换为dfa的方法，包括如下步骤：
4、1)定义自动机模型：
5、1-1)定义一个确定性有限状态自动机dfa(deterministic finite automaton，简称dfa)，dfa是一个五元组，用g表示：
6、g＝(x，∑，δ，x0，xm)，
7、其中，x为有限状态集，∑为字母表，δ：x×∑→x为状态转移函数，x0∈x为g的初始状态，为g的标记状态集，字母表∑是一个非空的有限字符集，一个字符串由∑中的字符组成，一组字符串构成一个语言，两个字符串s1，s2∈∑*的连接用s1.s2表示，简写为s1s2，对于状态x，y∈x和σ∈∑，转移函数δ(x，σ)＝y表示状态x经过字符σ转移到状态y，如果δ(x，σ)有定义，用δ(x，σ)！表示，转移函数δ采用以下递归的方式从定义域x×∑扩展到定义域x×∑*：
8、1-1-1)δ(x，ε)＝x，其中ε表示空字符；
9、1-1-2)对于s∈σ*和σ∈∑，如果δ(x，sσ)有定义，则δ(x，sσ)＝δ(δ(x，s)，σ)，一般来说，δ是部分有定义的，即可能存在x∈x和σ∈∑，使得δ(x，σ)没有定义，在∑上定义的一个语言l是由∑中的字符形成的有限长度字符串的集合，∑*表示定义在∑上所有有限长度字符串的集合，包括空字符串ε，∑上的一个语言l是∑*子集，g产生的语言记为l(g)＝{s∈σ*|δ(x0，s)！}，g标记的语言记为lm(g)＝{s∈∑*|δ(x0，s)＝xm)，如果字符串u，v，w∈∑*，并且字符串s＝u·v·w，则u称为字符串s的前缀，v称为字符串s的子串，w称为字符串s的后缀，且ε和s都是s的前缀、子串和后缀，pre(l)和suf(l)分别表示语言l中所有字符串的所有前缀和后缀的集合；
10、假设1：当语言l中所有的字符串的前缀也是语言l的成员时，则语言l是前缀闭合的，即pre(l)＝l；
11、假设2：当语言l中所有的字符串的后缀也是语言l的成员时，则语言l是后缀闭合的，即suf(l)＝l；
12、假设3：如果存在一个字符串s∈∑*，状态x∈x，有δ(x0，s)！且x＝δ(x0，s)，那么称状态x是可达的；
13、假设4：对于一个dfa g＝(x，∑，δ，x0，xm)，如果对于都是可达的，且对于存在字符串s∈∑*，都有δ(x1，s)≠δ(x2，s)成立，那么就称g为规范化的dfa；
14、1-2)定义一个非确定性有限状态自动机nfa(non-deterministic finite stateautomaton，简称nfa)，nfa是一个五元组，用gnd表示：
15、gnd＝(x，∑∪{ε}，δnd，x0，xm)，
16、其中，x为有限状态集，∑为字母表，ε为空字符串，δnd：x×∑∪{ε}→2x为状态转移函数，表示在gnd中经过同一个字符可能到达的状态，即为gnd的初始状态，为gnd的标记状态集；
17、在gnd中，根据字符的可观察性将字符分为可观字符集∑o和不可观字符集∑uo，同时满足∑o∪∑uo＝∑，
18、假设5：在gnd中，将状态x经过ε能到达的所有状态称为x的空可达状态集，这个集合用εr(x)来表示，并且x∈εr(x)：
19、εr(x)：＝δnd(x，ε)，
20、其中，对于一个状态练有εr(b)＝∪x∈bεr(x)且
21、与dfa类似，转移函数δnd采用以下递归的方式从定义域x×∑扩展到定义域x×∑*：
22、1-2-1)δnd(x，ε)＝εr(x)；
23、1-2-2)对于某些状态y∈δnd(x，u)，有z∈δnd(y，σ)，δnd(x，uσ)＝εr[z]，其中u∈∑*，σ∈∑，x，y∈x；
24、δnd(x，u)表示状态x经过字符串u到达的状态集，当δnd(x，u)中的某些状态y使得δnd(y，σ)！，对所有属于δnd(y，σ)的状态z计算空可达状态集δnd(x，uσ)；
25、2)将nfa转换为dfa：采用l*的学习框架，将gnd作为学习目标，gnd是部分定义的，即定义新的成员查询和等价查询来学习gnd，具体为：
26、输入：nfa gnd＝(x，∑∪{ε}，δnd，x0，xm)；
27、输出：dfa m＝(x0，∑，δ，x′0，x′m)；包括：
28、初始化s和e为{λ}；
29、对于每个s∈(s∪s·∑)·e执行成员查询，t(s)＝mq(s)；//mq(s)由步骤2-1)实现；
30、重复：
31、
32、直到cex＝null，停止学习，输出m；
33、首先将观察表初始化为s＝e＝{λ}，对每个s∈(s∪s·∑)·e执行成员查询，将查询的结果填入观察，然后重复执行以下步骤：
34、①判断一致性：对观察表进行一致性判断，如果在s，∑，e中找到使得row(s1)＝row(s2)，且t(s1·σ·e)≠t(s2·σ·e)的s1，s2，σ和e，其中s1，s2∈s，σ∈∑，e∈e，t(s1·σ·e)表示由行s1·σ和列e定位的内容，σ·e添加到e，然后对每个s∈(s∪s·∑)·{σ·e}执行成员查询并更新观察表，再对新的观察表进行一致性判断，直到观察表中如果row(s1)＝row(s2)，那么对于∑中的所有σ，都有row(s1·σ)＝row(s2·σ)成立，则称这个观察表是一致的，才进行下一步；
35、②判断闭合性：如果在s和s·∑中找到使得row(s1·σ)≠row(s)的s1和σ，其中s1∈s和σ∈∑，并且t(s1·σ)≠2，就将s1·σ添加到s，然后对每个s∈(s∪s·∑)·{σ·e}执行成员查询，并更新观察表，直到对于每个t∈s·∑且t(t)≠2，都有s∈s，使得row(t)＝row(s)，则称这个观察表是闭合，此时就进行下一步，其中对于一个s∈s∪s·∑，e∈e，row(s)表示从e到{0，1，2}的映射函数f，f＝t(s，e)，不能将t(s1·σ)＝2的s1·σ添加到s中是因为这样的row(s1·σ)表示的状态是一个dump_state，dump_state用于接收所有没有定义的转移，假设row(s1·σ)表示的状态为y，对于x∈x0，σ∈∑，如果δ(x，σ)没有定义，则令y＝δ(x，σ)，这样的y称为dump_state；
36、③构建假设，当得到一致且闭合的观察表后，就在字母表∑上定义一个与观察表(s，e，t)对应的dfa，该dfa是一个五元组，用m表示：
37、m＝(x0，∑，δ，x′0，x′m)，
38、其中：
39、x0＝{row(s)|s∈s}，
40、x′0＝row(λ)，
41、x′m＝{row(s)|s∈s且t(s)＝1}，
42、δ(row(s)，σ)＝row(s·σ)；
43、同样m可能是一个部分定义的dfa，因此，当δ(row(s)，σ)＝row(s·σ)中的t(s·σ)＝2时，证明δ(row(s)，σ)是没有定义的，在构建m的过程中不存在这样的转移；
44、④等价查询：目的在于判断是否得到了一个与学习目标gnd语言等价的dfa m，执行完等价查询后就会返回一个反例cex，如果cex≠mull，就证明gnd和m的语言还存在差异，就将pre(cex)添加到s，对(pre(cex)∪pre(cex)·∑)·e执行成员查询并更新观察表；
45、⑤重复步骤①到步骤④，直到cex＝null，证明学习到一个与gbd语言等价的dfa m，此时就将m输出，作为最终学习到的模型，具体为：
46、2-1)成员查询mq(s)：成员查询的答案为判断s是否属于l(gnd)和是否属于lm(gnd)的结果，即：
47、
48、具体过程由以下步骤实现：
49、成员查询算法mq(s)
50、输入：字符串s＝σ0σ1σ2σ3…σn，当n＝0时，s＝σ0＝λ，σi是s的第i个字符；
51、gnd＝(x，∑∪{ε}，δnd，x0，xm)；
52、输出：查询结果out；
53、
54、
55、其中，计算b的空可达状态集εr(b)为：
56、空可达算法εr(b)
57、输入：gnd＝(x，∑∪{ε}，δnd，x0，xm)；
58、一个状态集
59、输出：状态集d；
60、初始化
61、重复：
62、
63、其中，输入gnd和一个状态集初始化状态集对于每个x∈b，初始化一个状态集来存储δnd(x，ε)，如果δnd(x，ε)！，就将δnd(x，ε)和b存储到d中，同时将就将δnd(x，ε)存储到q中，直到b中的状态都计算完毕，说明已经b中已经没有能发生ε转移的状态了，此时返回d就是最终所求的空可达状态集；
64、当|s|＝0时，输入λ进行查询，此时b中只有x0，因为δnd(x0，λ)＝x0，不会发生状态的转换，所以判断εr(x0)是否存在标记状态，如果存在标记状态就返回mq(λ)＝out＝1，否则返回mq(λ)＝out＝0；
65、当|s|＞0时，在查询s之前首先初始化当前状态集b＝{x0}，表示从初始状态开始查询字符串，初始化一个集合set用于存储εr(b)中每个x′经过σi到达的状态构成的集合，首先计算b的εr(b)，对于每个x′∈εr(b)，如果δnd(x′，σi)！就将δnd(x′，σi)存储到set中，然后判断set是否为空，如果说明对于每个x′∈εr(b)，δnd(x′，σi)都没有意义，返回mq(s)＝out＝2，如果就令b＝set作为查询下一个字符的当前状态集，直到查询到最后一个字符σi，i＝|s|时，才计算εr(b)，如果εr(b)中存在标记状态，返回mq(s)＝out＝1，否则返回mq(s)＝out＝0；
66、2-2)等价查询eq(m)：等价查询为判断当前构造的假设自动机m和gnd的语言是否等价：①如果不等价就将反应m和gnd之间语言差异的字符串cex作为反例返回，反例用来对所构造的m进行改进；②如果m和gnd的语言等价就将m作为最终学习到的模型返回，用|t|表示t的长度，其中ti∈pre(t)，表示pre(t)中长度为i的字符串，i∈{123，…，|t|}，具体过程为：
67、等价查询算法eq(m)
68、输入：m＝(x0，∑，δ，x′0，x′m)；
69、gnd＝(x，∑∪{ε}，δnd，x0，xm)；
70、(s，e，t)中的s和e；
71、输出：cex；
72、
73、对于每个x∈xo，s∈s，首先判断row(s)是不是表示x的行，如果x＝row(s)说明s是构成x的字符串，s作为测试用例t的前缀，将然后随机生成一个字符串u∈∑*，作为测试用例t的子串，从e中随机取一个字符串v，作为测试用例t的后缀，此时得到测试用例t＝s·u·v，然后从i＝1的ti开始分别判断ti是否属于m和gnd的标记语言或生成语言，如果字符串或者就将ti作为反例输出，即反例cex＝ti，其中表示当符号两边判断结果相同时，运算结果为假，当符号两边判断结果不同时，运算结果为真，如果ti∈lm(m)⊙ti∈lm(gnd)或者ti∈l(m)⊙ti∈l(gnd)，那么就继续查询下一个字符串，直到i＝|t|，依旧没有找到反例，才重新构造一个t进行查询，其中⊙表示当符号两边判断结果相同时，运算结果为真，当符号两边判断结果不同时，运算结果为假，当x0＝{row(s)|s∈s}中的所有s都参与了t的构造，仍然没有发现cex后才会返回null来表示没有找到反例，在观察表中可能会存在s1，s2∈s，使得row(s1)＝row(s2)的情况，这在m(s，e，t)中表示的是同一个状态，因此只取表示m状态的s；
74、3)复杂度分析：复杂度与对观察表请求的成员查询次数有关，其中，|x|表示的gnd的状态数量，|∑|表示的∑的大小，令n＝|x|，k＝|∑|，m为最长反例的长度，在最坏情况下m有2n个状态，首先，初始化后e中已经存在一个元素，每次观察表不闭合时向e中添加一个字符串，最多进行2n-1次一致性判断，e中最多有2m个字符串，并且任何字符串的长度都不超过2n，每次观察表不闭合时向s中添加一个字符串，最多进行2n-1次闭合性判断，进行等价查询得到的最长反例为m，最多向s中添加m个字符串，最多生成2n-1个反例，s中最多有2n+m(2n-1)个字符串，s字符串的最大长度为m+2n-1，查询的字符串最多为o(km22n)，查询的字符串的长度最大为m+2n+1-1，，当|s|＝0时，计算初始状态的空可达状态集，计算出空可达的复杂度为o(n)，当|s|＞0时，|s|最大为m+2n+1-1，最多查询m+2n+1-1个字符，每次查询需要计算两次空可达状态集，空可达状态集最大为2n，最多需要重复查询2n次σi，复杂度为o(km223n+km24n+1)。
75、现有技术中将nfa转换为dfa过程为：
76、在cassandras和lafortune的《introduction to discrete event systems》一书中描述了一种将nfa的转换成dfa的算法，主要有以下几个步骤：
77、输入一个nfa gnd＝(x，∑∪{ε}，δnd，x0，xm)，输出一个dfa gobs＝(xobs，∑，δobs，x0，obs，xm，obs)，构建过程如下：
78、步骤1：定义gobs的初始状态为x0，obs，其结果为x0的空可达状态集，即x0，obs＝εr(x0)，随后将x0，obs添加到gobs的状态集中，即xobs＝{x0，obs}；
79、步骤2：在gobs中，对于每个b∈xobs和σ∈∑，有随后将δobs(b，σ)添加到xobs中；
80、步骤3：重复步骤2直到gnd所有的可达部分都已经构建完成；
81、步骤4：定义gobs的标记状态是包含xm的一个状态集；
82、由gnd转换的gobs有以下几个重要的性质：
83、1)gobs是一个确定性自动机即dfa；
84、2)l(gobs)＝l(gnd)；
85、3)lm(gobs)＝lm(gnd)；
86、cassandras和lafortune公开的方法的时间复杂度为o(2n)，本技术方案实现的是一种新的将nfa转换为dfa的方法，这种基于l*算法的方法能够将nfa直接转换为规范化的dfa，对于部分可观的目标模型来说，显然更简化的等价模型对于分析和控制来说更为容易。
87、这种方法将nfa作为被学习系统，不断提出查询、完善观察表，然后做出假设，生成反例不断更新假设，最终学习到与nfa语言等价的dfa模型，这种方法保证转换后的模型的状态最小化，为nfa转换为dfa提供了一种新的思路和方法。
1.一种基于l*算法将nfa转换为dfa的方法，其特征在于，包括如下步骤：
