LISP中的NFA识别器

Question

我必须在lisp中定义一个函数，给定一个正则表达式和一个e作为输入，如果该表达式被自动机接受，它将返回true。

首先，我定义了一个函数，它使用这些运算符{AC.26，*，+，.}从正则表达式生成e(作为反单元格)。

例如:对于表达式(或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))

我想出了一个想法:我编写了函数recognize or (处理或用例)：

(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

我将从一个高层次开始，把细节写下来。我不会给出一个完整的答案，因为它并不短，但希望它将足以使你走上正确的道路。

给定正则表达式和e作为输入，如果自动机接受表达式，则返回true。

为了简单起见，我将假设正则表达式是以一种与字母E中的字符串和通常的(, ), +, *兼容的形式给出的。我还假设e-NFA是以一种形式给出的，该表单包含所有必要的信息，以构成您在e-NFA的正式定义中所期望的所有信息。不考虑在实际格式和我喜欢的格式之间转换的困难。

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

如果e-NFA M是L(M)的子集，则L(r)接受正则表达式r。

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

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

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。剩下的唯一问题是:我们笛卡尔产品机器的语言是空的还是空的？

回答这个问题的方法很多，但最直接的方法是执行一个从初始状态开始的图搜索算法，看看是否可以到达任何接受状态。如果图搜索显示状态是可访问的，那么语言中就有一些字符串。如果从初始状态无法到达的任何状态都不接受，则语言是空的。任何有向图的搜索算法--深度优先，宽度优先，等等--都会很好。注意，图不是无圈图，所以不要使用任何需要无圈图的方法。

Answer 2

我想我已经知道你想做什么了。

编辑:我以为你在尝试将正则表达式转换成else，但你似乎想做些别的事情。无论如何，我现在还是留着这个吧。

让我们尝试在创建函数re->enfa方面取得一些进展，该函数接受以下参数：

1. 某种Lisp格式的正则表达式
2. 表示状态的符号，该状态将具有与此正则表达式相对应的epsilon转换到sub的转换。
3. 对应的离开状态的符号。

我们将使用符号来识别状态，这样我们就可以很容易地找到唯一的标识符。如果我们改变主意，我们会写一些小的函数

(defun new-state () (gensym))
(defun transition (from to on) `((delta ,from ,on ,to)))
(defun nfa-union (&rest args) (apply #'append args))

现在让我们来看两个例子，我们将把它们放在函数中。一个用于连接两个正则表达式，另一个用于交替。

(defun concat-nfa (a b s0 sn)
  (let ((m (new-state)))
    (nfa-union (re->enfa a s0 m) (re->enfa a m sn))))
(defun or-nfa (a b s0 sn)
  (let ((s1 (new-state))
        (s2 (new-state))
        (sk (new-state))
        (sl (new-state)))
    (nfa-union (transition s0 s1 'epsilon)
               (transition s0 s2 'epsilon)
               (transition sk sn 'epsilon)
               (transition sl sn 'epsilon)
               (re->enfa a s1 sk)
               (re->enfa b s2 sl))))

然后，您可以定义re->enfa的样子：

(defun re->enfa (x s0 sn)
  (if (atom x) (transition s0 sn x)
    (case (car x)
      (or (if (cddr x) (or-nfa (cadr x) (cons 'or (cddr x) s0 sn)
              (re->enfa (cadr x) s0 sn)))
      (concat  (if (cddr x) (concat-nfa (cadr x) (cons 'concat (cddr x) s0 sn)
              (re->enfa (cadr x) s0 sn)))
      (* (kleene-nfa (cadr x) s0 sn))
      (+ (re->nfa `(concat ,(cadr x) (* ,(cadr x))))))))

这应该给你一个起点，还有一些事情要补。还有一些你可以做的改变。例如，您可能希望以一种只需要为内部表达式计算一次的e的方式来实现+。

您还需要添加一个函数，该函数添加初始和最终状态的标记并包装re->enfa。