New answers tagged automata-theory
4
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 ...
12
No, the exponential lower bound for determinization holds already for unambiguous NFAs. This is obtained as follows:
Consider the alphabet $\{a,b\}$, and the language:
$$L_k=\{w\in \{a,b\}^*:\text{the $k$-th before last letter in }w\text{ is }b\}$$
It's easy to construct an unambiguous NFA for $L_k$: the NFA guesses when the $k$ before last letter is, and ...
Top 50 recent answers are included