search

RunDevelopment / refa

A library for finite automata and regular expressions in the context of JS RegExp
MIT License
20 stars 3 forks source link

`shortestAcceptingPath` will loop indefinitely for FAs with trap states #33

Closed RunDevelopment closed 3 years ago

RunDevelopment commented 3 years ago

If the iterator of an FA has a trap state (a state that cannot reach or is not a final state but has outgoing transitions) and that trap states can reach itself, then the shortestAcceptingPathwill loop forever.

However, forever may not be too long since it will continuously consume memory, quickly reaching the memory limit of the JS runtime.

RunDevelopment commented 3 years ago

Nevermind. I didn't read a line of code in my own algorithm...