![]() ![]() In the construction there might be many states that contain the original final state. Is the answer direct from the construction, or do we need KMP?Ī little observation. My question is the following: will the standard determinization of a "substring $w$" automaton always lead to a linear sized automaton? Here I mean the practical version of the construction, where unreachable states are not constructed (so not the full $2^Q$ subset construction). Luke has used KMP to provide an automaton for the example "not ABCDABD" in his answer Automaton for substring matching. That means that the deterministic automaton for "contains substring $w$" is of linear size too (failure links can be replaced by transitions, on for each mismatching letter). However, Knuth-Morris-Pratt tells us that a pattern match automaton for $w$ is of linear size, and can be constructed in linear time. When asked to make a deterministic automaton in general we might expect that the automaton can be of exponential size (see the warning of Yuval in the case where $w=101$: Write a regex to match string that does NOT contain a certain pattern). Just make the path for $w$ and add looped transitions for all letters at the first initial state and the last final state. A (non-deterministic) finite state automaton for "all strings that contain substring $w$" is very simple. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |