从正则表达式到NFA和DFA

Question

我有以下正则表达式：

[A−Z]∗01∗[^A−Z]{3}

字母是[A-Z][0-9]。

有人可以解释转换为NFA然后转换为DFA的正确方法。以及如何在C中实现epsilon封闭。

Answer 1

实施DFA。

---

让\0表示NUL（零字符）令\1等于[A−Z]令\2等于[^A−Z01] aka [2-9]

[^[A−Z]*01*[^A−Z]{3}\z变为^\1*01*[01\2][01\2][01\2]\0

这在某些情况下需要回溯才能实现。例如，处理与0111\0匹配的输入需要回溯。

DFA不支持回溯。 powerset contruction可以将NFA正式转换为DFA，但我将无需手动进行回溯。

上面的模式等同于下面的模式，不需要回溯（一旦提取了公共前缀）：

^ \1* 0
( 1 1 1 1* \0
| 1 1 1 1* [0\2] \0
| 1 1 1 1* [0\2] [01\2] \0
| 1 1 1 1* [0\2] [01\2] [01\2] \0
| 1 1 [0\2] \0
| 1 1 [0\2] [01\2] \0
| 1 1 [0\2] [01\2] [01\2] \0
| 1 [0\2] [01\2] \0
| 1 [0\2] [01\2] [01\2] \0
| [0\2] [01\2] [01\2] \0
)

---

让我们按前缀分组：

^ \1* 0
( 1 ( 1 ( 1 1* ( \0
               | [0\2] ( \0
                       | [01\2] ( \0
                                | [01\2] \0
                                )
                       )
               )
        | [0\2] ( \0
                | [01\2] ( \0
                         | [01\2] \0
                         )
                )
        )
    | [0\2] [01\2] ( \0
                   | [01\2] \0
                   )
    )
| [0\2] [01\2] [01\2] \0
)

---

现在，我们有了一种无需回溯的模式，可以轻松实现为DFA。但是在此之前，让我们通过合并相同的状态进行一些优化。

让<X>定义一个状态，然后让(?X)跳转到该状态。

^ \1* 0
( 1 ( 1 ( 1 1* ( \0 (?S02)
               | [0\2] <S04> ( \0 (?S02)
                             | [01\2] <S03> ( \0 (?S02)
                                            | [01\2] \0 (?S02)
                                            )
                             )
               )
        | [0\2] (?S04)
        )
    | [0\2] [01\2] (?S03)
    )
| [0\2] [01\2] [01\2] \0 (?S02)
)
<S02>

---

开始实施的时间。让我们结束定义状态。

开始状态：S01接受状态：S02

^ <S01> \1* 0
<S05> ( 1 <S06> ( 1 <S07> ( 1 <S08> 1* ( \0 (?S02)
                                       | [0\2] <S04> ( \0 (?S02)
                                                     | [01\2] <S03> ( \0 (?S02)
                                                                    | [01\2] <S09> \0 (?S02)
                                                                    )
                                                     )
                                       )
                          | [0\2] (?S04)
                          )
                | [0\2] <S10> [01\2] (?S03)
                )
      | [0\2] <S11> [1\2] <S12> [01\2] <S13> \0 (?S02)
      )
<S02>

---

因此，我们得到以下状态转换表：

      \0  \1   0   1  \2
S01      S01 S05          // Starting state
S02                       // Accepting state
S03  S02     S09 S09 S09
S04  S02     S03 S03 S03
S05          S11 S06 S11
S06          S10 S07 S10
S07          S04 S08 S04
S08  S02     S04 S08 S04
S09  S02                
S10          S03 S03 S03
S11          S12 S12 S12
S12          S13 S13 S13
S13  S02                

空白是我们称为S00的拒绝状态。

---

实施时间！

#include <stdio.h>

/*
   0        = 00     => 0
   'A'..'Z' = 41..5A => 1
   '0'      = 30     => 2
   '1'      = 31     => 3
   '2'..'9' = 32..39 => 4
*/

#define _ -1

static int char_to_input[0x80] = {
    0, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _,  // 00..0F
    _, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _,  // 10..1F
    _, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _,  // 20..2F
    2, 3, 4, 4, 4, 4, 4, 4, 4, 4, _, _, _, _, _, _,  // 30..3F
    _, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  // 40..4F
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, _, _, _, _, _,  // 50..5F
    _, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _,  // 60..6F
    _, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _,  // 70..7F
};

#define _ 0

static int transitions[14][5] = {
   {  _,  _,  _,  _,  _ },  // Reject
   {  _,  1,  5,  _,  _ },  // Start
   {  _,  _,  _,  _,  _ },  // Accept
   {  2,  _,  9,  9,  9 },
   {  2,  _,  3,  3,  3 },
   {  _,  _, 11,  6, 11 },
   {  _,  _, 10,  7, 10 },
   {  _,  _,  4,  8,  4 },
   {  2,  _,  4,  8,  4 },
   {  2,  _,  _,  _,  _ },
   {  _,  _,  3,  3,  3 },
   {  _,  _, 12, 12, 12 },
   {  _,  _, 13, 13, 13 },
   {  2,  _,  _,  _,  _ },
};

#undef _

enum {
   STATE_START  = 1,
   STATE_ACCEPT = 2,
   STATE_REJECT = 0,
};

int main(int argc, char** argv) {
   if (argc != 2) {
      fprintf(stderr, "usage\n");
      return 2;
   }

   const char *str = argv[1];
   size_t i = 0;
   int state = STATE_START;
   while (1) {
      unsigned char ch = (unsigned char)str[i];
      if (ch >= 0x80) {
         state = STATE_REJECT;
      } else {
         int input = char_to_input[ch];
         if (input < 0) {
            state = STATE_REJECT;
         } else {
            state = transitions[state][input];
         }
      }

      if (state == STATE_REJECT) {
         fprintf(stderr, "Not a match. (Failed at offset %zu.)\n", i);
         return 1;
      }

      if (state == STATE_ACCEPT) {
         fprintf(stdout, "Match.\n");
         return 0;
      }

      ++i;
   }
}

（（我使用_使其他值突出。）