4 ms·
It depends on the representation. If the representation is in the FSA format (state, character, state), it becomes nearly trivial.
by tgv 7y ago
It depends on the representation. If the representation is in the FSA format (state, character, state), it becomes nearly trivial.
- ggrrhh_ta 7y agoVery underrated comment. Very good point to give food for thought although I think it is clear that it was meant to be on the usual textual representation using the simplest re language (without extensions).
- morelisp 7y agoAn analogous problem for this representation would be detecting transitions to undefined states, or ambiguous (duplicate) transitions.
- tgv 7y agoI didn't verify it, but my intuition says that can't be done with a CFG; it seems at least context-sensitive.
- deleted 7y ago[deleted]