Autom

二年前就学习了形式语言与自动机，但一直没有机会完成相关代码。最近抽出时间，严格按照哈工大王春宇的《形式语言与自动机》的数学定义，使用 hashmap 和 hashset 实现了 DFA、NFA、ε-NFA。未来会完整地实现整个形式语言与自动机。

ps：automaton 名字已被占用，只能使用 autom

hashmap 的查找优势

(q，a)作为key，p作为value，来构建ε-NFA状态转移函数δ: Q X ∑ -> Q。

其中 q是当前状态，a是输入字符，p是转移状态，Q是有穷状态集，∑是字母表。

查找优势

在当前状态下，可能会遇到不同的字符。如果使用tree，只能遍历，时间复杂度是O(n)。使用hashmap，时间复杂度是O(1)。hashmap的查找效率更高。

hashset 的合并优势

在 NFA 中，可以有多个转移状态。所以每一次状态转移，都会涉及状态集合的合并。

合并优势

在 ε-NFA 中，如果有 ε 边，ε 闭包运算 Eclose(q) 又会增加集合的合并运算次数。

我们知道，hashset 合并的复杂度是 O( min{ a, b } )。而使用排序后的vector进行集合合并的时间复杂度是 O( a + b )。显然 hashset 的合并效率更高。

DFA 和 ε-NFA 使用方法

这个 DFA 实现了，在任何由 0 和 1 构成的串中，接受含有 01 子串的全部串。

let dfa = DFA {
    start: 0,
    delta: hashmap![
        (0, '1') => 0,
        (1, '1') => 2,
        (2, '1') => 2,
        (0, '0') => 1,
        (1, '0') => 1,
        (2, '0') => 2
    ],
    F: hashset![2],
};
assert!(dfa.accept("01"));
assert!(!dfa.accept("10"));
assert!(!dfa.accept("11"));

这个 ε-NFA 实现了，在任何由 0 和 1 构成的串中，接受倒数 3 个字符至少有一个是 1 的全部串。

let nfa = NFA {
    start: 0,
    delta: hashmap![
        (0, Some('0')) => hashset!(0),
        (0, Some('1')) => hashset!(0, 1),
        (1, Some('0')) => hashset!(2),
        (1, Some('1')) => hashset!(2),
        (1, None) => hashset!(2),
        (2, Some('0')) => hashset!(3),
        (2, Some('1')) => hashset!(3),
        (2, None) => hashset!(3)
    ],
    F: hashset!(2),
};
assert!(nfa.accept("01"));
assert!(nfa.accept("10"));
assert!(nfa.accept("11"));
assert!(!nfa.accept("100000"));
assert!(!nfa.accept("11000"));