<p>The paper <a href="https://ieeexplore.ieee.org/abstract/document/1671797" rel="noreferrer">Ambiguity in Graphs and Expressions (Book et al., 1971)</a> discusses constructing regular expressions that preserve the ambiguity of the input NFA and vice versa.</p>
<p>That is, they give a definition for &quot;ambiguity&quot; 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.</p>
<p>It relates to your question in that the class of unambiguous regular expressions, by their definition, would produce an unambiguous NFA using their construction.</p>

CC BY-SA 4.0
2021-10-14T18:11:29.300Z
2021-10-14T18:11:29.300Z
MRC
<p><a href="https://link.springer.com/chapter/10.1007%2F3-540-55210-3_182" rel="noreferrer">Brüggemann-Klein and Wood (1992)</a> 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.</p>
<p>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 <span class="math-container">$\varepsilon$</span>-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)?</p>

<reference-request><automata-theory><regular-language><regular-expressions>
Regular Expressions that converts into unambiguous automata
ricardorr
# Regular Expressions that converts into unambiguous automata

(Asked by: username_0 on 2021-10-13)

[Brüggemann-Klein and Wood (1992)](https://link.springer.com/chapter/10.1007%2F3-540-55210-3_182) 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)?

**Tags:** reference-request, automata-theory, regular-language, regular-expressions


---

## 1 answers

### Answer by username_1 on 2021-10-14. Score: 7 | Accepted answer

The paper [Ambiguity in Graphs and Expressions (Book et al., 1971)](https://ieeexplore.ieee.org/abstract/document/1671797) 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.


---

