Autom

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

ps：automaton名字已经有人占用，只能用autom

hashmap的查找优势

(q，a)作为key，p作为value，来构建ε-NFA状态转移函数$$ δ: Q\times∑ \rightarrow 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 {
	Q: 3,
    Sigma: vec!['0', '1'],
    delta: hashmap![
        (1, '1') => 1,
        (2, '1') => 3,
        (3, '1') => 3,
        (1, '0') => 2,
        (2, '0') => 2,
        (3, '0') => 3
    ],
    start: 1,
    F: hashset![3],
};
assert!(dfa.accept("01"));
assert!(!dfa.accept("10"));
assert!(!dfa.accept("11"));

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

let nfa = NFA {
    Q: 3,
    Sigma: vec!['0', '1'],
    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)
    ],
    start: 0,
    F: hashset!(3),
};
assert!(nfa.accept("01"));
assert!(nfa.accept("10"));
assert!(nfa.accept("11"));
assert!(!nfa.accept("100000"));
assert!(!nfa.accept("11000"));