lisp - LISP 中的 NFA 识别器

Question

我必须在 中定义一个函数口齿不清 即，给定一个正则表达式和一个 e-NFA 作为输入，如果该表达式被自动机接受，则返回 true。

首先，我定义了一个函数，它使用这些运算符 {|、*、+、...} 从正则表达式生成 e-NFA(作为 cons-cell)。

例如:使用表达式(或 a b)，输出将是:

((INITIAL 0) (DELTA 0 EPSILON 1) (DELTA 0 EPSILON 3) (DELTA 2 EPSILON 5) (DELTA 4 EPSILON 5) (DELTA 1 A 2) (DELTA 3 B 4) (FINAL 5))

我想出了这个想法:我编写了函数识别或(它处理或案例):

(defun nfa-recognize-or (fa input init final)
 (let ((arc (cdr (car fa))))
  (cond ((and (equal (first arc) init) (equal (second arc) 'epsilon))
         (nfa-recognize-or (cdr fa) input (third arc) final))
        ((not (equal (first arc) init))
         (nfa-recognize-or (cdr fa) input init final))
        ((and (equal (first arc) init) (equal (second arc) (car input)))
         (nfa-recognize-or fa (cdr input) (third arc) final))
        ((equal (third arc) final)
         T)
  )
 )
)

如果我这样调用函数:

(nfa-recognize-or (cdr fa) '(a) 0 5)

它返回“堆栈溢出”。问题是，经过一些调用，fa 的值 =

(DELTA 1 A 2) (DELTA 3 B 4) (FINAL 5))

与以前一样 init = 2 和 final = 5。此时，程序应该考虑的下一个状态应该是

(DELTA 2 EPSILON 5)

为了返回 TRUE，但这是不可能的，因为此时 NFA 已“消耗”，我无法回溯它以验证其他状态。

你有什么建议吗？

Answer 1

我将从高层次开始，然后深入研究细节。我不会给出完整的答案，因为它并不短，但希望它足以让你走上正确的道路。

given a regular expression and an e-NFA as input, it returns true if the expression is accepted by the automata.

为简单起见，我假设正则表达式以与字母表E中的字符串兼容的形式给出。加上通常的 (, ), +, * .我还假设 e-NFA以包含所有必要信息的形式给出，以构成您在 e-NFA 的正式定义中所期望的所有信息。 .将不考虑在实际格式和我的首选格式之间进行翻译的难度。

我总是建议在编写任何代码之前弄清楚如何手动解决问题。你会如何在测试中解决这个问题？如何判断 e-NFA接受正则表达式？更根本的是，对该要求的合理解释是什么？我的解释如下:

An e-NFA M accepts a regular expression r if L(r) is a subset of L(M).

换句话说，如果 w是由 r 匹配的字符串, 它应该被 M 接受.第一步很重要，因为它将问题转化为我们可以开始正式解决的问题。我们需要看看一件事的语言是否是另一件事的语言的子集。对于我所知道的正则表达式，没有直接的正式机制可以直接回答这个问题。然而，有一个众所周知的结构可以用有限自动机回答这样的问题:我将这种结构称为笛卡尔积机器结构，它用于产生一个有限自动机，它接受基于其他两种语言的语言有限自动机。特别是:如果 L \ R = 0 (其中 0 是空集，\ 是集差)，那么 L是 R 的子集.笛卡尔积机器构造允许我们为 L \ R 构造机器。给定机器 L和 R .我们已经有一个 M ;它是给定的。我们所需要的只是一台用于 L(r) 的机器我们已经准备好继续使用确定性算法来生产机器以适应不同的语言。然后，剩下的就是检查生成的语言是否为空。笛卡尔积机器构造的详细信息，见我的另一个回答here .不要担心你会有NFA小号；施工工作与 DFA 相同，如 here 所述.

给定一个正则表达式 r ，有一种算法可以产生 NFA接受 L(r) .我没有现成的链接，所以我会掩饰它。基本上，我们定义了一些递归规则来构造e-NFA。 s 基于正则表达式的每一项。以下是规则:

1. Alphabet symbol a: M(a)

--->()-a->(O)


2. Concatenation rs: M(rs)

--->[M(r)]-e->[M(s)]

* Note: one -e-> from each accepting state of M(r) to initial state of M(s)
        initial state is that of M(r)
        accepting states are those of M(s)


3. M(r+s):

-->()-e->[M(r)]
    \-e->[M(s)]

* Note: new initial state added
        accepting states are those of M(r) and M(s)

4. M(r*):

     /--e--\
    V       \
--->()-e->[M(r)]

* Note: one -e-> from each accepting state of M(r) to initial state
        new initial state
        accepting state is only the new initial state

现在，我们为您的正则表达式提供了 NFA，并且我们知道如何构建笛卡尔积机器来解决这个问题。我们最终得到的是一个大的e-NFA表示L(r)的差异和 L(M) .我们已经说过，这些语言的区别是空的，当且仅当 L(r)是 L(M) 的子集, 和 L(r)是 L(M) 的子集如果M接受 r .剩下的唯一问题是:我们笛卡尔积机器的语言是否为空？

有很多方法可以回答这个问题，但最直接的方法是从初始状态开始执行图搜索算法，看看是否有任何接受状态是可达的。如果图形搜索显示某个状态是可达的，那么该语言中有一些字符串。如果从初始状态可到达的状态均未接受，则语言为空。任何有向图的搜索算法——深度优先、广度优先等——都可以。请注意，该图不是非循环的，因此不要使用任何需要非循环图的方法。