6 releases
0.1.5 | Dec 28, 2023 |
---|---|
0.1.4 | Dec 10, 2023 |
0.1.3 | Jun 30, 2022 |
#303 in Math
19KB
442 lines
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"));