There are two principal methods for turning regular expressions into NFA's - one due to McNaughton and Yamada and another due to Thompson. Unfortunately, both have drawbacks. Given a regular expression R of length r and with s occurrences of alphabet symbols, Chang and Paige (1992) and Bruggemann-Klein(1993) gave Theta(m+r) time and O(r) spate algorithms to produce a Theta(m) space representation of McNaughton and Yamada's NFA with s+1 states and in transitions. The problem with this NFA is that m=Theta(s(2)) in the worst case. Thompson's method takes Theta(r) time and space to construct a Theta(r) space NFA with Theta(r) states and Theta(r) transitions. The problem with this NFA is that r can be arbitrarily larger than s. We overcome drawbacks of both methods with a Theta(r) time Theta(s) space algorithm to construct an O(s) space representation of McNaughton and Yamada's NFA. Given any set V of NFA states, our representation can be used to compute the set U of states one transition away from the states in V in optimal time O(V+U). McNaughton and Yamada's NFA requires Theta(VxU) time in the worst case. Using Thompson's NFA, the equivalent calculation requires Theta(r) time in the worst case. Comparative benchmarks show that an implementation of our method outperforms implementations of competing methods with respect to time for NFA construction, NFA accepting testing, and NFA-to-DFA conversion by subset construction. Throughout this paper program transformations are used to design algorithms and derive programs. A transformation of special importance is a form of finite differencing used previously by Douglas Smith to improve the efficiency of functional programs. [References: 26]
展开▼
机译：将正则表达式转换为NFA的主要方法有两种-一种是McNaughton和Yamada提出的，另一种是Thompson提出的。不幸的是，两者都有缺点。给定长度为r的正则表达式R并出现s个字母符号，Chang and Paige（1992）和Bruggemann-Klein（1993）给出了Theta（m + r）时间，O（r）的spate算法产生了Theta（m ）McNaughton和Yamada的NFA在s + 1状态和过渡状态下的空间表示。这个NFA的问题是在最坏的情况下m = Theta（s（2））。汤普森的方法需要花费Theta（r）时间和空间来构建具有Theta（r）状态和Theta（r）过渡的Theta（r）空间NFA。这个NFA的问题在于r可以比s任意大。我们使用Theta（r）时间Theta（s）空间算法克服了这两种方法的缺点，以构造McNaughton和Yamada的NFA的O（s）空间表示形式。给定NFA状态的任何集合V，我们的表示可用于计算在最佳时间O（ V + U ）中距离V中的状态一个跃迁的状态集合U。麦克诺顿和山田的NFA在最坏的情况下需要Theta（ V x U ）时间。使用汤普森的NFA，在最坏的情况下，等效计算需要Theta（r）时间。比较基准表明，在NFA构建，NFA接受测试以及子集构建NFA到DFA转换的时间方面，我们的方法的实施要优于竞争方法的实施。在整个本文中，程序转换用于设计算法和派生程序。特殊重要性的转换是道格拉斯·史密斯（Douglas Smith）先前使用的有限差分形式，用于提高功能程序的效率。 [参考：26]
展开▼
