<p>As observed in the proof of Theorem 6 (later dubbed the &quot;Star Height Lemma&quot;) of Gruber/Holzer ICALP 2008, when converting a regular expression into an <span class="math-container">$\varepsilon$</span>-NFA, then the underlying graph has treewidth at most <span class="math-container">$2$</span>.  This implies that the graph has undirected cycle rank at most <span class="math-container">$2\log n$</span> by Corollary 3.1 in Gruber JoC 2012. (Undirected cycle rank soon thereafter became better known as tree-depth.) In Gruber/Holzer IJFCS 2013, the problem of converting an <span class="math-container">$n$</span>-state NFA into a regular expression is studied as a parameterized problem; we can convert an <span class="math-container">$n$</span>-state <span class="math-container">$\varepsilon$</span>-NFA of undirected cycle rank <span class="math-container">$k$</span> into an equivalent regular expression of size <span class="math-container">$|\Sigma|\cdot 4^k \cdot n$</span> (Theorem 9).</p>
<p>Putting it together, we obtain a bound of <span class="math-container">$|\Sigma|\cdot 4^{2 \log n} \cdot n = |\Sigma| \cdot n^5$</span>, which is polynomial in <span class="math-container">$n$</span> as desired.</p>
<p>I assume that the bound will not be reached in the worst case.</p>
<p>References:</p>
<ul>
<li>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.</li>
<li>Hermann Gruber. On Balanced Separators, Treewidth, and Cycle Rank. Journal of Combinatorics, 3(4):669-682, 2012.</li>
<li>Hermann Gruber and Markus Holzer. Provably Shorter Regular Expressions From Finite Automata. International Journal of Foundations of Computer Science, 24(8):1255-1279, 2013.</li>
</ul>

CC BY-SA 4.0
2023-12-22T13:33:11.010Z
Many thanks for the answer. This result is amazing! Could you please tell me whether the bound holds is we assume that the desired automaton is free of epsilon-transitions?
Bartosz Bednarczyk
CC BY-SA 4.0
2023-12-22T16:08:30.367Z
Bartosz, the series parallel structure of the Thompson construction seems essential for the treewidth 2 argument. I am pretty sure that no analogous results are known for e-free NFAs.
Hermann Gruber
CC BY-SA 4.0
2023-12-22T12:56:44.193Z
2023-12-22T12:56:44.193Z
Hermann Gruber
<p>Suppose that a regular expression <span class="math-container">$\mathcal{R}$</span> over an alphabet <span class="math-container">$\Sigma$</span> is given. It is well-known that one can now construct a non-deterministic finite automaton <span class="math-container">$\mathcal{A}$</span> such that <span class="math-container">$\mathcal{R}$</span> and <span class="math-container">$\mathcal{A}$</span> recognize the same languages. Let <span class="math-container">$\mathcal{A}_{q,q'}$</span> be an automaton obtained from <span class="math-container">$\mathcal{A}$</span> by changing its initial state to <span class="math-container">$q$</span> and its final state to <span class="math-container">$q'$</span> (where <span class="math-container">$q, q'$</span> are from the state-space of <span class="math-container">$\mathcal{A}$</span>). My question is:</p>
<blockquote>
Is this the case for every regular expression <span class="math-container">$\mathcal{R}$</span> that there exists an equivalent NFA <span class="math-container">$\mathcal{A}$</span> of size polynomial w.r.t <span class="math-container">$\mathcal{R}$</span> such that for all pairs of states <span class="math-container">$(q,q')$</span> the automata <span class="math-container">$\mathcal{A}_{q,q'}$</span> have equivalent regular expressions <span class="math-container">$\mathcal{R}_{q,q'}$</span> of size polynomial w.r.t <span class="math-container">$\mathcal{R}$</span>?  
</blockquote> 
<p>I'm aware that generally, a regular expression may be of size exponential w.r.t. the input automaton. However, in this case, such an automaton comes from another regular expression; thus, it is unclear to me what the answer should be.
To clarify: I use the standard definition of regular expressions from Sipser's book so the syntax of regular expressions is as follows:</p>
<p>
<span class="math-container">$
\mathcal{R} ::= a \in \Sigma \mid \varepsilon \mid \emptyset \mid \mathcal{R} \cup \mathcal{R} \mid \mathcal{R} \circ \mathcal{R} \mid \mathcal{R}^*. 
$</span>
</p>
In particular, extra features such as complementation and intersection are not allowed.

CC BY-SA 4.0
2023-12-18T14:35:47.310Z
Observation that may be helpful identifying edge cases. I think the following holds: let $R$ be a regular expression with $*$-depth $k$ and $A$ the automaton constructed from $R$ via Thompson's construction. Then for every $q_1,q_2$ in $A$, there exists a regular expression $R[q_1,q_2]$ matching $A_{q_1,q_2}$ of size at most $3^k|R|$. This is an induction on $R$. The only "challenging" case is when $R=S^*$, with $R[q_1,q_2] = S[q_1,q_f] (S[q_0,q_f])^* S[q_f, q_2]$ where $q_0,q_f$ are the initial/final state of $S$. It triples the size of the regexp. For bounded depth of $*$, that should work.
holf
CC BY-SA 4.0
2023-12-18T15:36:29.210Z
Unfortunately in my case the star depth can be unbounded. So do you think that the answer to my question is probably negative?
Bartosz Bednarczyk
CC BY-SA 4.0
2023-12-19T14:35:24.320Z
No idea, just trying to identify where the naive approach breaks ;)!
holf
CC BY-SA 4.0
2023-12-19T18:38:48.617Z
I think the focus should be on the follow-up question, because if you put no constraint on how A is produced, you can always put in A complicated parts that recognize the same language but will induce exponential expressions. It is for instance trivial when A is not required to be pruned, then you can just add an unreachable part A' next to it.
Denis
CC BY-SA 4.0
2023-12-19T19:58:27.313Z
Dear Denis, you are of course right! Thanks a lot for your observation. I've just updated my post to fully focus on the follow-up question.
Bartosz Bednarczyk
<automata-theory><regular-language><regular-expressions><nfa>
The complexity of conversion from a regular expression to a nondeterminsitic automata and back after changing initial and final states
Bartosz Bednarczyk
# The complexity of conversion from a regular expression to a nondeterminsitic automata and back after changing initial and final states

(Asked by: username_0 on 2023-12-17)

Suppose that a regular expression $\mathcal{R}$ over an alphabet $\Sigma$ is given. It is well-known that one can now construct a non-deterministic finite automaton $\mathcal{A}$ such that $\mathcal{R}$ and $\mathcal{A}$ recognize the same languages. Let $\mathcal{A}\_{q,q'}$ be an automaton obtained from $\mathcal{A}$ by changing its initial state to $q$ and its final state to $q'$ (where $q, q'$ are from the state-space of $\mathcal{A}$). My question is:

> Is this the case for every regular expression $\mathcal{R}$ that there exists an equivalent NFA $\mathcal{A}$ of size polynomial w.r.t $\mathcal{R}$ such that for all pairs of states $(q,q')$ the automata $\mathcal{A}\_{q,q'}$ have equivalent regular expressions $\mathcal{R}\_{q,q'}$ of size polynomial w.r.t $\mathcal{R}$?

I'm aware that generally, a regular expression may be of size exponential w.r.t. the input automaton. However, in this case, such an automaton comes from another regular expression; thus, it is unclear to me what the answer should be.
To clarify: I use the standard definition of regular expressions from Sipser's book so the syntax of regular expressions is as follows:

$
\mathcal{R} ::= a \in \Sigma \mid \varepsilon \mid \emptyset \mid \mathcal{R} \cup \mathcal{R} \mid \mathcal{R} \circ \mathcal{R} \mid \mathcal{R}^\*.
$

In particular, extra features such as complementation and intersection are not allowed.

**Tags:** automata-theory, regular-language, regular-expressions, nfa
> **Comments:**
> **username_1**: Observation that may be helpful identifying edge cases. I think the following holds: let $R$ be a regular expression with $*$-depth $k$ and $A$ the automaton constructed from $R$ via Thompson's construction. Then for every $q_1,q_2$ in $A$, there exists a regular expression $R[q_1,q_2]$ matching $A_{q_1,q_2}$ of size at most $3^k|R|$. This is an induction on $R$. The only "challenging" case is when $R=S^*$, with $R[q_1,q_2] = S[q_1,q_f] (S[q_0,q_f])^* S[q_f, q_2]$ where $q_0,q_f$ are the initial/final state of $S$. It triples the size of the regexp. For bounded depth of $*$, that should work.  
> **username_0**: Unfortunately in my case the star depth can be unbounded. So do you think that the answer to my question is probably negative?  
> **username_1**: No idea, just trying to identify where the naive approach breaks ;)!  
> **username_2**: I think the focus should be on the follow-up question, because if you put no constraint on how A is produced, you can always put in A complicated parts that recognize the same language but will induce exponential expressions. It is for instance trivial when A is not required to be pruned, then you can just add an unreachable part A' next to it.  
> **username_0**: Dear Denis, you are of course right! Thanks a lot for your observation. I've just updated my post to fully focus on the follow-up question.  

---

## 1 answers

### Answer by username_3 on 2023-12-22. Score: 8 | Accepted answer

As observed in the proof of Theorem 6 (later dubbed the "Star Height Lemma") of Gruber/Holzer ICALP 2008, when converting a regular expression into an $\varepsilon$-NFA, then the underlying graph has treewidth at most $2$. This implies that the graph has undirected cycle rank at most $2\log n$ by Corollary 3.1 in Gruber JoC 2012. (Undirected cycle rank soon thereafter became better known as tree-depth.) In Gruber/Holzer IJFCS 2013, the problem of converting an $n$-state NFA into a regular expression is studied as a parameterized problem; we can convert an $n$-state $\varepsilon$-NFA of undirected cycle rank $k$ into an equivalent regular expression of size $|\Sigma|\cdot 4^k \cdot n$ (Theorem 9).

Putting it together, we obtain a bound of $|\Sigma|\cdot 4^{2 \log n} \cdot n = |\Sigma| \cdot n^5$, which is polynomial in $n$ as desired.

I assume that the bound will not be reached in the worst case.

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. On Balanced Separators, Treewidth, and Cycle Rank. Journal of Combinatorics, 3(4):669-682, 2012.
* Hermann Gruber and Markus Holzer. Provably Shorter Regular Expressions From Finite Automata. International Journal of Foundations of Computer Science, 24(8):1255-1279, 2013.

> **Comments:**
> **username_0**: Many thanks for the answer. This result is amazing! Could you please tell me whether the bound holds is we assume that the desired automaton is free of epsilon-transitions?  
> **username_3**: Bartosz, the series parallel structure of the Thompson construction seems essential for the treewidth 2 argument. I am pretty sure that no analogous results are known for e-free NFAs.  

---

