#automata

bin+lib autom

Automaton

6 releases

0.1.5 Dec 28, 2023
0.1.4 Dec 10, 2023
0.1.3 Jun 30, 2022

#303 in Math

MIT license

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

No runtime deps