从正则表达式到 NFA 再到 DFA

Question

我有以下正则表达式：

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

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

谁能解释一下转换为 NFA 然后再转换为 DFA 的正确方法。以及如何在 C 中实现 epsilon 闭包。

Answer 1

使用 ε 步法 (NFA-ε) 实施 NFA

首先，在这种特殊情况下，36 个字符的字母表可以减少到 4 个独占类。

让</code>表示<code>[A−Z]
让 </code> 表示 <code>[^A−Z01] 又名 [2-9]

这将我们的字母表缩减为 </code>、<code>0、1 和 </code>。</p> <p><code>[A−Z]*01*[^A−Z]{3} 变为 *01*[01]{3}

Thompson's construction 可用于将正则表达式转换为 NFA-ε。

*01*[01]{3} 等价于 *01*[01][01][01]，所以我们得到：

我们可以使用上面描述的状态图为 NFA-ε 生成以下转换 table：

      ε             0       1       
      ------- ------- ------- ------- -------
S00   S01,S03                                   Starting State
S01           S02
S02   S01,S03
S03                   S04
S04   S05,S07
S05                           S06
S06   S05,S07
S07                   S08     S08     S08
S08                   S09     S09     S09
S09                   S10     S10     S10
S10                                             Accepting State

当然也很明显也可以用下面的NFA:

实现起来会简单得多，因为实现 NFA 引擎比实现 NFA-ε 引擎要简单得多。但是，通过以下步骤将 NFA-ε 转换为 NFA 是微不足道的：

展平递归 ε 移动。

例如，

S00--ε-->{S01}
S01--ε-->{S02}
S02--ε-->{S03}
S02--1-->{S04}

变成

S00--ε-->{S01,S02,S03}
S01--ε-->{S02,S03}
S02--ε-->{S03}
S02--1-->{S04}

合并通过 ε 移动达到的状态转换。

例如，

S00--ε-->{S01,S02,S03}
S01--ε-->{S02,S03}
S02--ε-->{S03}
S03--1-->{S04}

变成

S00--ε-->{S01,S02,S03}
S00--1-->{S04}
S01--ε-->{S02,S03}
S01--1-->{S04}
S02--ε-->{S03}
S02--1-->{S04}
S03--1-->{S04}

将通过ε-移动到达接受状态的状态添加到接受状态集合。
下降 ε-移动。

对于我们的 NFA-ε，我们得到以下信息：

我们可以更进一步，清理 NFA。

存在可以移除的不可达状态。（S01、S03、S05、S07不可达）
有相同的状态可以组合。（S00和S02有相同的转换，S04和S06也有相同的转换。）

执行这些清理后，我们得到

是不是很眼熟？

是时候实施了！下面实现了上面的 NFA-ε，但在处理输入之前使用上面的步骤自动将其转换为 NFA。（它不执行任何清理步骤。）

#include <stdio.h>
#include <stdint.h>


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

#define NUM_INPUTS 5

#define _ -1

static int char_to_input[0x80] = {
    _, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _,  // 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
};

#undef _


#define S(x) (1 << x)
#define S00 (1 <<  0)
#define S01 (1 <<  1)
#define S02 (1 <<  2)
#define S03 (1 <<  3)
#define S04 (1 <<  4)
#define S05 (1 <<  5)
#define S06 (1 <<  6)
#define S07 (1 <<  7)
#define S08 (1 <<  8)
#define S09 (1 <<  9)
#define S10 (1 << 10)

#define _ 0

static uint_least16_t transitions[][NUM_INPUTS] = {
   //       ε  ,     ,    0  ,    1, ,   
   // -------  ,  ---  ,  ---  ,  ---  ,  ---
   {  S01|S03  ,  _    ,  _    ,  _    ,  _    },   // S00   Starting State
   {  _        ,  S02  ,  _    ,  _    ,  _    },   // S01
   {  S01|S03  ,  _    ,  _    ,  _    ,  _    },   // S02
   {  _        ,  _    ,  S04  ,  _    ,  _    },   // S03
   {  S05|S07  ,  _    ,  _    ,  _    ,  _    },   // S04
   {  _        ,  _    ,  _    ,  S06  ,  _    },   // S05
   {  S05|S07  ,  _    ,  _    ,  _    ,  _    },   // S06
   {  _        ,  _    ,  S08  ,  S08  ,  S08  },   // S07
   {  _        ,  _    ,  S09  ,  S09  ,  S09  },   // S08
   {  _        ,  _    ,  S10  ,  S10  ,  S10  },   // S09
   {  _        ,  _    ,  _    ,  _    ,  _    },   // S10   Accepting State
};

#undef _

uint_least16_t STATES_START  = S00;
uint_least16_t STATES_REJECT = 0;
uint_least16_t STATES_ACCEPT = S10;

#define NUM_STATES (sizeof(transitions)/sizeof(transitions[0]))


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

   // Flatten recursive ε-moves.
   for (size_t s1=0; s1<NUM_STATES; ++s1) {
      uint_least16_t e_states = transitions[s1][0];

      do {
         for (size_t s2=0; s2<NUM_STATES; ++s2) {
            if (e_states & S(s2))
               e_states |= transitions[s2][0];
         }
      } while (e_states != transitions[s1][0]);

      transitions[s1][0] = e_states;
   }

   // Convert NFA-ε into NFA.
   {
      // For each state s1,
      // for each state s2,
      // if s1 has an ε-move to s2,
      // merge s2's transitions into s1's.
      for (size_t s1=0; s1<NUM_STATES; ++s1) {
         uint_least16_t e_states = transitions[s1][0];
         for (size_t s2=0; s2<NUM_STATES; ++s2) {
            if (e_states & S(s2)) {
               for (size_t i=1; i<NUM_INPUTS; ++i) {
                  transitions[s1][i] |= transitions[s2][i];
               }
            }
         }
      }

      // For each state s1,
      // for each accepting state s2,
      // if s1 has an ε-move to s2,
      // add s1 to the set of accepting states.
      for (size_t s1=0; s1<NUM_STATES; ++s1) {
         uint_least16_t e_states = transitions[s1][0];
         uint_least16_t Ss1 = S(s1);
         if (!(STATES_ACCEPT & Ss1)) {
            for (size_t s2=0; s2<NUM_STATES; ++s2) {
               if (e_states & S(s2) & STATES_ACCEPT) {
                  STATES_ACCEPT |= Ss1;
                  break;
               }
            }
         }
      }
   }

   // NFA engine
   {
      const char *str = argv[1];
      size_t i = 0;
      uint_least16_t states = STATES_START;
      while (1) {
         unsigned char ch = (unsigned char)str[i];
         if (!ch) {
            if (states & STATES_ACCEPT) {
               fprintf(stdout, "Match.\n");
               return 0;
            }
         }

         if (ch >= 0x80) {
            states = STATES_REJECT;
         } else {
            int input = char_to_input[ch];
            if (input < 0) {
               states = STATES_REJECT;
            } else {
               uint_least16_t new_states = STATES_REJECT;
               for (size_t s=0; s<NUM_STATES; ++s,states>>=1) {
                  if (states & 1)
                     new_states |= transitions[s][input];
               }

               states = new_states;
            }
         }

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

         ++i;
      }
   }
}

（我使用 _ 使非平凡的值脱颖而出。）

可以使用 powerset contruction 将 NFA 转换为 DFA，但这样做没有多大意义。

从正则表达式到 NFA 再到 DFA

From a regular expression to NFA and to DFA

c

regex

dfa

nfa