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子串的全部串。

rust 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的全部串。

rust 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"));