Closed akumm2k closed 2 years ago
The bug seems to be in the minimization of dfa.
reg_to_dfa = minimize . nfa_to_dfa . reg_to_nfa
> n = reg_to_nfa "ab*|ba*"
> d' = nfa_to_dfa n
> d' `accepts` "aba"
False
The dfa from the nfa to dfa conversion rejects "aba" correctly.
The bug is manifested in minimization here:
> d
Q: [0,1,2]
delta: [(0 - a -> 1),(0 - b -> 2),(1 - b -> 1),(2 - a -> 2)]
q0: 0
F: [1,2]
> d `accepts` "aba"
False
> d' = minimize d
> d'
Q: [0,1]
delta: [(0 - a -> 1),(0 - b -> 1),(1 - a -> 1),(1 - b -> 1)]
q0: 0
F: [1]
> d' `accepts` "aba"
True
The DFA produced here is incorrect.
The NFA produced here correctly accepts "aba".