How do finite state automata handle ambiguity

Although, in the worst case, they can run slowly, you can steer them to find matches in linear or polynomial time by using patterns that reduce ambiguities and limit backtracking. Traditional NFA engines are favored by programmers because they offer greater control over string matching than either DFA or POSIX NFA engines. As a result, a POSIX NFA engine is slower than a traditional NFA engine, and when you use a POSIX NFA engine, you cannot favor a shorter match over a longer one by changing the order of the backtracking search. POSIX NFA engines are like traditional NFA engines, except that they continue to backtrack until they can guarantee that they have found the longest match possible. Because a traditional NFA engine accepts the first match it finds, it can also leave other (possibly longer) matches undiscovered. As a result, it can run exponentially slowly in the worst case. However, because a traditional NFA backtracks, it can visit the same state multiple times if it arrives at the state over different paths. Because a traditional NFA engine constructs a specific expansion of the regular expression for a successful match, it can capture subexpression matches and matching backreferences. NFA engines use backtracking to test all possible expansions of a regular expression in a specific order and accept the first match. This process of abandoning a successful subexpression match so that later language elements in the regular expression can also match is known as backtracking. If a match eventually fails, the engine can return to a saved state so it can try additional matches. But it also saves its state after successfully matching a subexpression. As it processes a particular language element, the engine uses greedy matching that is, it matches as much of the input string as it possibly can. Unlike DFA engines, when traditional NFA engines perform pattern matching, their processing order is driven by the regular expression pattern. However, because a DFA engine contains only finite state, it cannot match a pattern with backreferences, and because it does not construct an explicit expansion, it cannot capture subexpressions. Because they never test the same character twice, DFA engines do not support backtracking. They can guarantee to match the longest string possible. The engine begins at the beginning of the input string and proceeds sequentially to determine whether the next character matches the regular expression pattern. When DFA engines perform pattern matching, their processing order is driven by the input string. NET are implemented by using a traditional NFA engine. The following section describes the three types of regular expression engines, and explains why regular expressions in. This also distinguishes it from standardized, but slower, POSIX NFAs. This distinguishes it from faster, but more limited, pure regular expression Deterministic Finite Automaton (DFA) engines such as those found in awk, egrep, or lex. NET regular expression engine is a backtracking regular expression matcher that incorporates a traditional Nondeterministic Finite Automaton (NFA) engine such as that used by Perl, Python, Emacs, and Tcl.

How do finite state automata handle ambiguity