light0x00 · February 28, 2020 07:43 · Feb 28, 2020 · Feb 28, 2020 · Feb 28, 2020
diff --git a/subset-construct.js → subset_construct.js b/subset-construct.js → subset_construct.js
diff --git a/test.js b/test.js
@@ -0,0 +1,55 @@
+let subset_construct = require('./subset_construct')
+require('mocha')
+require('should')
+
+/**
+ * 模拟《编译原理》P98
+ */
+describe('============Subset Construction Test============', function () {
+
+    //字符集
+    let charset = ['a', 'b'];
+    //NFA转换表 
+    /*
+    NFA
+        a             b
+    0   {3,8}       {5}
+    1   {3}         {5}
+    2   {3}         \
+    3   {3,8}       {5}
+    4   \           {5}
+    5   {3,8}       {5}
+    6   {3,8}         {5}
+    7   {8}         \
+    8   \           {9}
+    9   \           {10}
+    */
+    let Ntran = {
+        0: { '': [1, 2, 4, 7], a: [3, 8], b: [5] },
+        1: { '': [2, 4], a: [3], b: [5] },
+        2: { '': [], a: [3], b: [] },
+        3: { '': [1, 2, 4, 6, 7], 'a': [3, 8], 'b': [5] },
+        4: { '': [], 'a': [], 'b': [5] },
+        5: { '': [1, 2, 4, 6, 7], 'a': [3, 8], 'b': [5] },
+        6: { '': [1, 2, 4, 7], 'a': [3, 8], 'b': [5] },
+        7: { '': [], 'a': [8], 'b': [] },
+        8: { '': [], 'a': [], 'b': [9] },
+        9: { '': [], 'a': [], 'b': [10] },
+        10: { '': [], 'a': [], 'b': [] },
+    }
+
+    //预期的的DFA转换表
+    let expected = require('./expected_dfa.json')
+
+    describe(`
+    charset: ${JSON.stringify(charset)}
+    NFA: ${JSON.stringify(Ntran)}
+    `, function () {
+        it(`expected ${JSON.stringify(expected)}`, function () {
+            let actual = subset_construct(charset, Ntran)
+            should.deepEqual(actual.Dtran, expected.Dtran)
+            should.deepEqual(actual.Dstates, expected.Dstates)
+
+        })
+    })
+})
diff --git a/subset-construct.js b/subset-construct.js
@@ -0,0 +1,67 @@
+const _ = require("lodash");
+
+/**
+ * 使用子集构造法,将NFA转为DFA. 基于《编译原理》P97的伪代码的实现.
+ * @param charset NFA所接受的字符集
+ * @param Ntran NFA转换表
+ */
+module.exports = function subset_construct(charset, Ntran) {
+    let cursor = 0; //区分Dstates中的状态集是否访问过. cursor之前的为已访问, cursor之后为未访问.
+
+    let Dstates = []  //DFA的状态集
+    let Dtran = {} //DFA的转换表
+    Dstates.push(e_closure([0])) //起始状态0输入e可到达的状态集
+
+    //遍历尚未标记的DFA状态 T
+    while (cursor < Dstates.length) {
+        let T = Dstates[cursor];
+        cursor++;
+        Dtran[T] = {}
+        for (let c of charset) {
+            let T_c = move(T, c)   //状态T 在输入c时可达的非空状态集 T_c
+            let T_e = e_closure(T_c)    //状态集 T_c 可达的
+            let U = combine(T_c, T_e)
+            //判断状态集U 是否已经存在于Dstates 不存在则放入
+            let exists = Dstates.find(states => states.length == U.length && _.difference(states, T).length == 0
+            ) != null
+            if (!exists) {
+                Dstates.push(U)
+            }
+            /* 
+            放入DFA转换表,这表示T在分别输入(charset U ε)中的每一个字符时,可达的状态集,
+            */
+            Dtran[T][c] = U
+        }
+    }
+
+    /**
+     * 返回给定状态集T输入ε可达的状态集
+     * @param {*} T 状态集T
+     */
+    function e_closure(T) {
+        let result = []
+        for (let s of T) {
+            result = combine(result, Ntran[s][''])
+            result = combine(result, e_closure(Ntran[s][''])) //递归寻找ε
+        }
+        return result
+    }
+    /**
+     * 返回给定状态集T输入c可达的状态集
+     * @param {*} T 状态集T
+     */
+    function move(T, input) {
+        let result = []
+        for (let s of T) {
+            result = combine(result, Ntran[s][input])
+        }
+        return result
+    }
+
+    return { Dstates, Dtran }
+}
+
+/* 工具性方法 */
+function combine(arr1, arr2) {
+    return _.sortBy(_.union(arr1, arr2))
+}
No results found