3
$\begingroup$

Consider the following recursive algorithm for converting a regular expression into a transition diagram for an NFA with epsilon-edges (freely, optionally traversible edges), one start state and one accept state:

  • To convert the concatenation of $R_1$ and $R_2$, draw the NFAs for both regular expressions, then draw an epsilon-edge from the accept state of the NFA for $R_1$ to the start state of the NFA for $R_2$.
  • To convert the union of $R_1$ and $R_2$, take the union of both graphs. Create and designate a new start state and accept state, then draw epsilon-edges from the new start state to the old start states and from the old accept states to the new accept state.
  • To convert the Kleene star of $R_1$, draw an epsilon-edge from the accept state of the NFA for $R_1$ to the start state, then designate the start state as also being the accept state.

For this and similar algorithms, the resulting NFA feels like it has some kind of hierarchical structure to it, with subexpressions of the regular expression corresponding to subgraphs of the NFA that are connected only in particular ways.

That makes me wonder: is there some utility in converting an NFA to a regular expression and then converting back to transform an NFA into an equivalent NFA whose transition diagram (although much bigger) had this nice structure?

More generally, is there some nontrivial property $P$ of transition diagrams that holds for the results of this (or maybe a similar) translation algorithm? I chose the particular algorithm above because the resulting graphs are always planar, but I don't know of any utility in having such a planar representation of a regular language. Is there some such property $P$ that is useful (perhaps for an algebraic decomposition)?

$\endgroup$
6
  • $\begingroup$ I don't understand the question. DFA and REGEXP are equivalent as far as expressive power: both recognize precisely the class of the regular languages. $\endgroup$
    – Aryeh
    Jan 22 at 13:39
  • $\begingroup$ Ah, here I'm using 'DFA' in a sense where two DFAs are equal if their transition diagrams are graph-isomorphic. I.e. there's some permutation of states that takes the start state, transition function, and accept states of one to the other. Certainly if we're just considering equivalence in terms of language accepted this question isn't interesting. $\endgroup$
    – TomKern
    Jan 22 at 14:25
  • 1
    $\begingroup$ Good point. For some reason I figured since you can do the construction recursively on the regular expression producing NFAs that are mostly DFAs, but have epsilon-edges (freely, optionally traversable edges), you could then easily remove the epsilon-edges to get a DFA. But the process of removing epsilon-edges gives you an NFA not a DFA. I suppose there's still an interesting nugget in this question which is 'is there value in turning a DFA into an untangled NFA?', but this not nearly as exciting. $\endgroup$
    – TomKern
    Jan 22 at 21:19
  • 3
    $\begingroup$ The question is not answerable. You have to define what you mean by "the naive recursive algorithm". There are multiple algorithms; and there are variations on some of the exact details. I encourage you to edit the question to clarify that point, and to address the issues raised in the prior comments. $\endgroup$
    – D.W.
    Jan 23 at 7:52
  • 1
    $\begingroup$ I think the question is a bit imprecise, but I think there is some meaning to it. The recursive algorithm described in the question is reminiscent of Thompson's construction (en.wikipedia.org/wiki/Thompson%27s_construction) and I agree that it looks like the resulting automata have some structure, that looks a bit like being series-parallel (en.wikipedia.org/wiki/Series%E2%80%93parallel_graph). I agree that it could be the case that there'd be some use to converting any NFA to an automata of this form by converting it to a regexp and back. That said, I don't have an example... $\endgroup$
    – a3nm
    Jan 24 at 20:13

1 Answer 1

2
$\begingroup$

In fact, this roundtrip conversion is used in the proof of the Star Height Lemma, and this in turn has lots of implications in the area of descriptional complexity of regular expressions. And here it comes...

The star height of a regular language $L$ is defined as the minimum star height among all regular expressions (using operations concatenation, union and Kleene star) describing $L$. Simple examples such as $(a(a(a(ab)^*b)^*b)^*b)^*$ show that the star height of a regular expression can be linear in its size, and there seem to be no obvious simplification that would yield a regular expression of lower height. Perhaps somewhat non-intuitively, we can always get away with a star height which is logarithmic in the minimum regular expression length.

The star height lemma can be used, for example, to show that regular expressions extended with a shuffle (interleaving) operator are doubly exponentially more succinct than ordinary regular expressions. Or that converting an NFA into a planar NFA will necessarily incur at least a quadratic size blow-up in the worst case (the upper bound is exponential).

Star Height Lemma: Let $L$ be a regular language, let $h(L)$ denote its star height, and let $\mathrm{alph}(L)$ denote the minimum size (alphabetic width) of a regular expression for $L$. Then $h(L) = O(\log (\mathrm{alph}(L)))$.

The Star Height Lemma is proved by observing that if we convert a regular expression into an NFA using Thompson's construction, the resulting NFA is a series-parallel when viewed as an undirected graph. This graph has treewidth 2, and tree-depth logarithmic in its size. This can be used to find an elimination ordering such that converting back to a regular expression using state elimination yields a regular expression of logarithmic star height (and polynomial size, which yet does not matter for the lemma).

References:

  • Hermann Gruber and Markus Holzer. Finite Automata, Digraph Connectivity, and Regular Expression Size. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), Reykjavik, Iceland, volume 5126 of Lecture Notes in Computer Science, pages 39-50. Springer, July 2008.

  • Hermann Gruber, Markus Holzer, and Martin Kutrib. Descriptional Complexity of Regular Languages. In Jean-Eric Pin, editor, Handbook of Automata Theory. Volume I: Theoretical Foundations, pages 411-458. European Mathematical Society Press, 2021.

$\endgroup$
1
  • $\begingroup$ Exciting and unexpected! Thanks! $\endgroup$
    – TomKern
    Feb 2 at 2:12

Your Answer

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

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