什么是 Glushkov NFA？Glushkov NFA 和 Thompson NFA 有什么区别？

Question

什么是 Glushkov NFA？Glushkov NFA 和 Thompson NFA 有什么区别？

automatacomputation-theorynfa

5

我在http://lambda-the-ultimate.org/node/2064看到了“Glushkov NFA”这个术语。搜索引擎返回了使用glushkov nfa的文章，但没有关于glushkov nfa本身的具体信息。

什么是Glushkov NFA？它与从Thompson Construction创建的NFA有何不同？

- woodstok

这听起来像是那种需要在http://cstheory.stackexchange.com/上寻找好答案的深度技术问题。 - glenatron

1

@glenatron：CSTheory仅适用于研究级别的问题。[cs.se]可能更合适。 - hammar

1

此外，本文解释了什么是Glushkov自动机：http://www.sciencedirect.com/science/article/pii/S030439759700296X - user4680559

2个回答

2

《在字符串中进行灵活的模式匹配》一文中，详细阐述了Glushkov自动机的定义。它是通过使用last、first、follow和nullable函数从正则表达式解析树构建的NFA。与Thompson Construction创建的NFA不同，这个NFA不包含空转移。请参考该文章获取更多信息：http://nlp.cs.swarthmore.edu/~richardw/cs93-f07/flexiblePatternMatchingInStrings.pdf。

- woodstok

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bryan Olivier · Accepted Answer

我找到了这篇文章《Glushkov、Follow和Antimirov自动机的统一构建》，其中包含了一个非确定有限状态自动机的Glushkov构造的定义。