5
$\begingroup$

Brüggemann-Klein and Wood (1992) proved that a certain kind of regular expressions, that they call “Deterministic Regular expressions”, when converted into automata using the Glushkov's Construction, generate a DFA. Also, all the expressions that generate a DFA via this algorithm are in this class.

Is something known about classes of regular expression that when given as input to some conversion algorithm to automata (Thompson, Glushkov, any algorithm that gives a NFA or $\varepsilon$-NFA in the general case) we get a unambiguous automaton (A NFA such that for every word in the language, only exists one acceptation run)?

$\endgroup$

1 Answer 1

7
$\begingroup$

The paper Ambiguity in Graphs and Expressions (Book et al., 1971) discusses constructing regular expressions that preserve the ambiguity of the input NFA and vice versa.

That is, they give a definition for "ambiguity" in regular expressions (how many valid parses are there for a given word), and show how to construct an NFA that will have the same number of accepting paths for each word. Or, given an NFA, how to construct a regular expression with the same property.

It relates to your question in that the class of unambiguous regular expressions, by their definition, would produce an unambiguous NFA using their construction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.