A New Translation from Semi-extended Regular Expressions into NFAs and Its Application to an Approximate Matching Problem
A New Translation from Semi-extended Regular Expressions into NFAs and Its Application to an Approximate Matching Problem
复制标题
DOI：
10.1007/978-3-540-24587-2_18
复制
发表时间：
2003-09
期刊：
影响因子：
--
通讯作者：
Hiroaki Yamamoto
中科院分区：
文献类型：
--
作者：
Hiroaki Yamamoto
半扩展正则表达式是具有交集的正则表达式。将正则表达式转换为不确定性有限自动机（nfa）的两种算法是众所周知的，即Thompson构造和Glushkov构造。将SEREs转换为NFAs的一种简单方法是使用Thompson构造，因为它可以很容易地应用于SEREs。似乎很难将格卢什科夫结构直接应用于SEREs。本文利用Glushkov构造和Yamamoto的模分解技术，提出了一种新的从SEREs到NFAs的转换方法。然后，给定一个具有mrintersection算子的serer0，我们可以生成一个最多有nr +1个状态和时间和空间跃迁的NFA。这里是由r的分解得到的一个数，并且小于由平凡平移（即使用Thompson结构的平移）得到的NFA的状态数。此外，我们将展示一个近似SERE匹配问题的应用。
Semi-extended regular expressions (SEREs) are regular expressions (REs) with intersection. Two algorithms for translating REs into nondeterministic finite automata (NFAs) are widely known, that is, Thompson construction and Glushkov construction. A trivial way for translating SEREs into NFAs is to use Thompson construction because it can easily be applied to SEREs. It seems to be difficult to directly apply Glushkov construction to SEREs. In this paper, we present a new translation from SEREs into NFAs using Glushkov construction and the modular decomposition technique by Yamamoto. Then, given an SERErwithmrintersection operators, we can generate an NFA with at mostNr+1 states andtransitions intime and space. HereNris a number obtained from the decomposition ofr, and is less than the number of states of an NFA obtained by the trivial translation (that is, the translation using Thompson construction). In addition, we will show an application to an approximate SERE matching problem.