<p>Your problem can be solved in polynomial time.</p>

<p>To begin, convert the given NFA to an equivalent NFA with the following additional properties:</p>

<ul>
<li>There are no epsilon transitions</li>
<li>All states are reachable from the start state</li>
</ul>

<h2>Helpful subroutine</h2>

<p>Suppose we have an NFA <span class="math-container">$N$</span>, a state <span class="math-container">$q$</span>, and a nonempty string <span class="math-container">$s$</span>. The following subroutine will let us evaluate the truth value of the following statement: "every path in <span class="math-container">$N$</span> from state <span class="math-container">$q$</span> to an accept state corresponds to a string that is a prefix of string <span class="math-container">$s^n$</span> for some <span class="math-container">$n$</span>." Furthermore, this subroutine will run in polynomial time.</p>

<p>First, construct the NFA <span class="math-container">$S$</span> with <span class="math-container">$|s| + 1$</span> states which accepts all strings that are not prefixes of <span class="math-container">$s^n$</span> for any <span class="math-container">$n$</span> (<span class="math-container">$|s|$</span> non-accept states in a loop to keep track of where in the "pattern" of <span class="math-container">$sssss\ldots$</span> we are so far, and one accept state for if we have already deviated from that pattern). Next, construct the NFA <span class="math-container">$N'$</span> which is exactly like <span class="math-container">$N$</span> but has <span class="math-container">$q$</span> as its start state. Finally, construct a final NFA <span class="math-container">$N''$</span> whose language <span class="math-container">$L(N'')$</span> is <span class="math-container">$L(S) \cap L(N')$</span> using the standard NFA intersection construction. Note that all of these constructions are polynomial in the size of the input.</p>

<p>Then simply test whether the language of <span class="math-container">$N''$</span> is empty (which can be done in polynomial time with a simple graph search). <span class="math-container">$L(N'') = \emptyset$</span> if and only if <span class="math-container">$L(S) \cap L(N') = \emptyset$</span>, or in other words every string in <span class="math-container">$L(N')$</span> is not in <span class="math-container">$L(S)$</span>. In other words, the language of <span class="math-container">$N''$</span> is empty if and only if <span class="math-container">$N'$</span> accepts only strings that are prefixes of <span class="math-container">$s^n$</span> for some <span class="math-container">$n$</span>. This can be rephrased as exactly the statement we were trying to evaluate: "every path in <span class="math-container">$N$</span> from state <span class="math-container">$q$</span> to an accept state corresponds to a string that is a prefix of string <span class="math-container">$s^n$</span> for some <span class="math-container">$n$</span>."</p>

<h2>Main algorithm</h2>

<p>Consider the set of states in the NFA that are in some loop. For each such state, <span class="math-container">$q$</span>, do the following:</p>

<p>Let <span class="math-container">$P_2$</span> be any simple loop containing <span class="math-container">$q$</span>. Let <span class="math-container">$s$</span> be the string corresponding to loop <span class="math-container">$P_2$</span>. Since the NFA has no epsilon transitions, <span class="math-container">$s$</span> is not empty. Then apply the subroutine to the NFA, state <span class="math-container">$q$</span>, and string <span class="math-container">$s$</span>. If the subroutine tells us that every path starting at <span class="math-container">$q$</span> in the NFA and ending at an accept state corresponds to a prefix of <span class="math-container">$s^n$</span> for some <span class="math-container">$n$</span> then continue to the next state <span class="math-container">$q$</span>. Otherwise, output that the given NFA's language contains an infinite prefex-free subset. </p>

<p>If we try every state <span class="math-container">$q$</span> that is in a loop and the algorithm never outputs, then output that the given NFA's language does not contain an infinite prefex-free subset.</p>

<h2>Correctness (first half)</h2>

<p>First, suppose that the above algorithm asserts that the given NFA's language contains an infinite prefex-free subset. Let's say that this output was selected while considering some loop <span class="math-container">$P_2$</span> and some state <span class="math-container">$q$</span>. As before, <span class="math-container">$s$</span> is the string corresponding to <span class="math-container">$P_2$</span>. Then we know according to the subroutine that not every path starting at <span class="math-container">$q$</span> in the NFA and ending at an accept state corresponds to a prefix of <span class="math-container">$s^n$</span> for some <span class="math-container">$n$</span> (as this is the only output of the subroutine that would lead to the main algorithm outputting at that <span class="math-container">$q$</span>).</p>

<p>Let <span class="math-container">$P_3$</span> be a path whose existence is asserted by the subroutine: a path from <span class="math-container">$q$</span> to an accept state such that the corresponding string <span class="math-container">$t$</span> is not a prefix of <span class="math-container">$s^n$</span> for any <span class="math-container">$n$</span>. </p>

<p>Let <span class="math-container">$P_2'$</span> consist of <span class="math-container">$m$</span> copies of <span class="math-container">$P_2$</span> where <span class="math-container">$m$</span> is sufficiently large that <span class="math-container">$m|s| &gt; |t|$</span>. Since <span class="math-container">$P_2$</span> is a loop through <span class="math-container">$q$</span>, <span class="math-container">$P_2'$</span> can be treated as a path from <span class="math-container">$q$</span> to <span class="math-container">$q$</span>. The string corresponding to <span class="math-container">$P_2'$</span> is <span class="math-container">$s^m$</span></p>

<p>Let <span class="math-container">$P_1$</span> be a path from the start state to <span class="math-container">$q$</span> (which exists since every state is reachable from the start) and let <span class="math-container">$r$</span> be the string corresponding to this path.</p>

<p>Then the path consisting of <span class="math-container">$P_1$</span>, <span class="math-container">$x$</span> copies of <span class="math-container">$P_2'$</span>, and <span class="math-container">$P_3$</span> is an accepting computation path. The string corresponding to this path is <span class="math-container">$r(s^m)^xt$</span>. Thus, the NFA accepts every string of the form <span class="math-container">$r(s^m)^xt$</span>. This is an infinite set of strings accepted by the NFA, and I claim that this set of strings is prefix-free. In particular, suppose <span class="math-container">$r(s^m)^xt$</span> is a prefix of <span class="math-container">$r(s^m)^yt$</span> with <span class="math-container">$y &gt; x$</span>. In other words, <span class="math-container">$t$</span> is a prefix of <span class="math-container">$(s^m)^{y-x}t$</span>. Since <span class="math-container">$(s^m)^{y-x}$</span> has length <span class="math-container">$m(y-x)|s| \ge m|s| &gt; |t|$</span>, this implies that <span class="math-container">$t$</span> is a prefix of <span class="math-container">$(s^m)^{y-x} = s^{m(y-x)}$</span>. But we know by the output of the subroutine that <span class="math-container">$t$</span> is not a prefix of <span class="math-container">$s^n$</span> for any <span class="math-container">$n$</span>. Thus, <span class="math-container">$r(s^m)^xt$</span> cannot be a prefix of <span class="math-container">$r(s^m)^yt$</span>, and as desired the set of strings is prefix-free. </p>

<p>Thus, I have shown that if the main algorithm outputs that the given NFA's language contains an infinite prefex-free subset then this is in fact the case.</p>

<h2>Correctness (second half)</h2>

<p>Next, I will show the other half: if the given NFA's language contains an infinite prefex-free subset then the main algorithm will output this fact.</p>

<p>Suppose the given NFA's language contains an infinite prefix-free subset. Let <span class="math-container">$A$</span> be the set of (accepting) computation paths corresponding to these strings. Notice that <span class="math-container">$A$</span> is an infinite set of accepting computation paths whose corresponding strings are never prefixes of each other.</p>

<p>Say that a state is "looping" in the NFA if there exists a loop in the NFA through that state and "non-looping" otherwise. Consider all paths from the start state to any looping state which pass through only non-looping states (except for the one looping state where they end up). Let <span class="math-container">$P$</span> be the set of these paths. Each path <span class="math-container">$p \in P$</span> cannot have a loop as then the states in that loop would be looping states and so <span class="math-container">$p$</span> would pass through a looping state. Thus, the lengths of paths in <span class="math-container">$P$</span> are bounded above by the number of states in the NFA and so <span class="math-container">$P$</span> is finite (for example, if the start state is a looping state then the only such path is the empty path). </p>

<p>We can partition <span class="math-container">$A$</span> into <span class="math-container">$|P|+1$</span> subsets based on how that computation paths in <span class="math-container">$A$</span> starts. In particular, for <span class="math-container">$p \in P$</span>, let <span class="math-container">$A_p$</span> be the set of all computation paths in <span class="math-container">$A$</span> that start with path <span class="math-container">$p$</span> and let <span class="math-container">$B$</span> be the set of all other paths in <span class="math-container">$A$</span>. Clearly, all <span class="math-container">$A_p$</span>s and <span class="math-container">$B$</span> are disjoint and their union is the entire set <span class="math-container">$A$</span>. Furthermore, <span class="math-container">$B$</span> contains only paths that never pass through a looping state, and therefore never loop; thus <span class="math-container">$B$</span> is finite. We can conclude then that some <span class="math-container">$A_p$</span> must be infinite (otherwise <span class="math-container">$A$</span> would be a union of finitely many finite sets).</p>

<p>Since <span class="math-container">$A_p$</span> is infinite, there are infinitely many computation paths, none of whose strings are prefixes of each other, that are accepting paths starting with <span class="math-container">$p$</span>. Let <span class="math-container">$q$</span> be the state reached at the end of path <span class="math-container">$p$</span>. We can conclude that there are infinitely many accepting paths, call this set <span class="math-container">$A'$</span>, starting at <span class="math-container">$q$</span> all of which correspond to strings that are not prefixes of each other. </p>

<p>During the main algorithm, we run the subroutine on state <span class="math-container">$q$</span> and some string <span class="math-container">$s$</span>. This subroutine tells us whether every accepting path starting at <span class="math-container">$q$</span> corresponds to a string that is a prefix of <span class="math-container">$s^n$</span> for some <span class="math-container">$n$</span>. If this were the case, then all the infinitely many accepting paths in <span class="math-container">$A'$</span> would be prefixes of <span class="math-container">$s^n$</span> for various <span class="math-container">$n$</span>, which would imply that they are all prefixes of each other. This is not the case, so we conclude that when the main algorithm runs the subroutine on state <span class="math-container">$q$</span>, the result is the other possible outcome. This, however, leads the main algorithm to output that the NFA's language contains an infinite prefix-free subset.</p>

<p>This concludes the proof of correctness.</p>

CC BY-SA 4.0
2018-12-28T00:02:06.630Z
I don't understand how the loop handling works, since a given state $q$ can be part of (exponentially) many loops. Of course, if any two of those loops can be used to generate a non-periodic sequence, then we are done.
japh
CC BY-SA 4.0
2018-12-28T01:32:29.323Z
What do you mean by loop handling? In the main algorithm, for each state $q$ you pick just one loop that goes through $q$ (any loop out of the potentially exponentially many) and call that loop $P_2$ (afterwords you run the subroutine on state $q$ and string $s$ where $s$ is the string associated with $P_2$). The subroutine essentially handles the check of whether it is possible to generate a non-periodic sequence using that loop. If yes, then we're done. If no (and furthermore no for every $q$), then your entire language is a union of periodic sequences so we're also done.
Mikhail Rudoy
CC BY-SA 4.0
2018-12-28T02:34:03.657Z
To make my question clearer, here's a simple NFA with initial state $q$, final state $T$ and three transitions: $q \overset{a}{\rightarrow} q$, $q \overset{b}{\rightarrow} q$, $q \overset{a}{\rightarrow} T$. The loop for $a$ will not generate the prefix-free strings, but the loop for $b$ will.
japh
CC BY-SA 4.0
2018-12-29T04:52:50.130Z
Actually, the loop for $a$ does generate a prefix free set: the set of strings $a^*ba$ all use the $a$ loop. In my algorithm, if the loop you choose for $q$ is the $a$ loop then the subroutine will determine that no, not every accepting path starting at $q$ has a string of the form $a^*$, and so the main algorithm will say that an infinite prefix-free subset exists. If the loop the algorithm uses for $q$ is instead the $b$ loop then the subroutine determines that not every accepting path starting at $q$ has a string of the form $b^*$, and in this case too the algorithm has the same output.
Mikhail Rudoy
CC BY-SA 4.0
2019-01-03T10:12:21.610Z
Thank you Mikhail! I think your answer settles the question.
Googlo
CC BY-SA 4.0
2018-12-27T22:40:17.230Z
2018-12-27T22:40:17.230Z
Mikhail Rudoy
<h2>Definitions</h2>

<p><strong>Definition 1</strong>: Let <span class="math-container">$S$</span> be a set of words. We say that <span class="math-container">$S$</span> is <em>nicely infinite prefix-free</em> (made up name for the purpose of this answer) if there are words <span class="math-container">$u_0,\dots,u_n,\dots $</span> and <span class="math-container">$v_1,\dots,v_n,\dots $</span> such that:</p>

<ul>
<li><p>For each <span class="math-container">$n\ge 1$</span>, <span class="math-container">$u_n$</span> and <span class="math-container">$v_n$</span> are non-empty and start with distinct letters;</p></li>
<li><p><span class="math-container">$S=\{u_0v_1,\dots,u_0\dots u_n v_{n+1},\dots\}$</span>.</p></li>
</ul>

<p>The intuition is that you can put all those words on an infinite rooted tree (the <code>■</code> is the root, the <code>▲</code> are the leaves, and the <code>•</code> are the remaining interior nodes) of the following shape such that the words in <span class="math-container">$S$</span> are exactly the labels of paths from the root to a leaf:</p>

<pre><code>   u₀    u₁    u₂
■-----•-----•-----•⋅⋅⋅
      |     |     |
      | v₁  | v₂  | v₃
      |     |     |
      ▲     ▲     ▲
</code></pre>

<p><strong>Proposition 1.1</strong>: A nicely infinite prefix-free set is prefix-free.</p>

<p><strong>Proof of proposition 1.1</strong>: Suppose that <span class="math-container">$u_0\dots u_n v_{n+1}$</span> is a strict prefix of <span class="math-container">$u_0 \dots u_m v_{m+1}$</span>. There are two cases:</p>

<ul>
<li><p>If <span class="math-container">$n &lt; m$</span> then <span class="math-container">$v_{n+1}$</span> is a prefix of <span class="math-container">$u_{n+1}\dots u_m v_{m+1}$</span>. This is impossible because <span class="math-container">$u_{n+1}$</span> and <span class="math-container">$v_{n+1}$</span> have distinct first letters.</p></li>
<li><p>If <span class="math-container">$n &gt; m$</span> then <span class="math-container">$u_{m+1}\dots u_n v_{n+1}$</span> is a prefix of <span class="math-container">$v_{m+1}$</span>. This is impossible because <span class="math-container">$u_{m+1}$</span> and <span class="math-container">$v_{m+1}$</span> have distinct first letters.</p></li>
</ul>

<p><strong>Proposition 1.2</strong>: A nicely infinite prefix-free set is infinite.</p>

<p><strong>Proof of proposition 1.2</strong>: In proof 1.1, we showed that if <span class="math-container">$n\not= m$</span> then <span class="math-container">$u_0\dots u_n v_{n+1}$</span> and <span class="math-container">$u_0 \dots u_m v_{m+1}$</span> are not comparable for the prefix order. They are therefore not equal.</p>

<hr>

<h2>Main proof</h2>

<p><strong>Proposition 2</strong>: Any infinite prefix-free set contains a nice infinite prefix-free set.</p>

<p><strong>Proposition 3</strong>: A language contains an infinite prefix-free set if and only if it contains a nicely infinite prefix-free set.</p>

<p>Proof below.</p>

<p><strong>Proof of proposition 3</strong>: <span class="math-container">$\boxed{\Rightarrow}$</span> by proposition 2. <span class="math-container">$\boxed{\Leftarrow}$</span> by propositions 1.1 and 1.2.</p>

<p><strong>Proposition 4</strong>: The set of nicely-prefix-free subsets of a regular language (encoded as an infinite word <span class="math-container">$\overline{u_0}\widehat{v_1}\overline{u_1}\widehat{v_2}\overline{u_2}\dots$</span>) is <span class="math-container">$\omega$</span>-regular (and the size of the Büchi automaton recognizing it is polynomial in the size of the NFA recognizing the regular language).</p>

<p>Proof below.</p>

<p><strong>Theorem 5</strong>: Deciding if a regular language described by a NFA contains an infinite prefix-free subset can be done in time polynomial in the size of the NFA.</p>

<p><strong>Proof of theorem 5</strong>: By proposition 3, it is sufficient to test if it contains a nicely-infinite prefix-free subset, which can be done in polynomial time by building the Büchi automaton given by proposition 4 and testing the non-emptyness of its language (which can be done in time linear in the size of the Büchi automaton).</p>

<hr>

<h2>Proof of proposition 2</h2>

<p><strong>Lemma 2.1</strong>: If <span class="math-container">$S$</span> is a prefix-free set, then so is <span class="math-container">$w^{-1}S$</span> (for any word <span class="math-container">$w$</span>).</p>

<p><strong>Proof 2.1</strong>: By definition.</p>

<p><strong>Lemma 2.2</strong>: Let <span class="math-container">$S$</span> be an infinite set of words. Let <span class="math-container">$w:=\operatorname{lcp}(S_n)$</span> be the longest prefix common to all words in <span class="math-container">$S$</span>. <span class="math-container">$S$</span> and <span class="math-container">$w^{-1}S$</span> have the same cardinal.</p>

<p><strong>Proof 2.2</strong>: Define <span class="math-container">$f:w^{-1}S\to S$</span> by <span class="math-container">$f(x)=wx$</span>. It is well defined by definition of <span class="math-container">$w^{-1}S$</span>, injective by definition of <span class="math-container">$f$</span> and surjective by definition of <span class="math-container">$w$</span>.</p>

<p><strong>Proof of proposition 2</strong>: We build <span class="math-container">$u_n$</span> and <span class="math-container">$v_n$</span> by induction on <span class="math-container">$n$</span>, with the induction hypothesis <span class="math-container">$H_n$</span> composed of the following parts:</p>

<ul>
<li><p><span class="math-container">$(P_1)$</span> For all <span class="math-container">$k\in\{1,\dots,n\}$</span>, <span class="math-container">$u_0\dots u_{k-1} v_k \in S$</span>;</p></li>
<li><p><span class="math-container">$(P_2)$</span> For all <span class="math-container">$k\in\{1,\dots,n\}$</span>, <span class="math-container">$u_k$</span> and <span class="math-container">$v_k$</span> are non-empty and start with distinct letters;</p></li>
<li><p><span class="math-container">$(P_3)$</span> <span class="math-container">$S_n:=(u_0\dots u_n)^{-1}S$</span> is infinite;</p></li>
<li><p><span class="math-container">$(P_4)$</span> There is no non-empty prefix common to all words in <span class="math-container">$S_n$</span>. In other words: There is no letter <span class="math-container">$a$</span> such that <span class="math-container">$S_n\subseteq a\Sigma^*$</span>.</p></li>
</ul>

<p><strong>Remark 2.3</strong>: If we have sequences that verify <span class="math-container">$H_n$</span> without <span class="math-container">$(P_4)$</span>, we can modify <span class="math-container">$u_n$</span> to make them to also satisfy <span class="math-container">$(P_4)$</span>. Indeed, it suffices to replace <span class="math-container">$u_n$</span> by <span class="math-container">$u_n\operatorname{lcp}(S_n)$</span>. <span class="math-container">$(P_1)$</span> is unaffected. <span class="math-container">$(P_2)$</span> is trivial. <span class="math-container">$(P_4)$</span> is by construction. <span class="math-container">$(P_3)$</span> is by lemma 3.</p>

<p>We now build the sequences by induction on <span class="math-container">$n$</span>:</p>

<ul>
<li><p>Initialization: <span class="math-container">$H_0$</span> is true by taking <span class="math-container">$u_0:=\operatorname{lcp}(S)$</span> (i.e. by taking <span class="math-container">$u_0:=\varepsilon$</span> and applying remark 3.1).</p></li>
<li><p>Induction step: Suppose that we have words <span class="math-container">$u_1,\dots,u_n$</span> and <span class="math-container">$v_1,\dots,v_n$</span> such that <span class="math-container">$H_n$</span> for some <span class="math-container">$n$</span>. We will build <span class="math-container">$u_{n+1}$</span> and <span class="math-container">$v_{n+1}$</span> such that <span class="math-container">$H_{n+1}$</span>.</p></li>
</ul>

<p>Since <span class="math-container">$S_n$</span> is infinite and prefix-free (by lemma 1), it does not contain <span class="math-container">$\varepsilon$</span> so that <span class="math-container">$S_n=\underset{a\in \Sigma}{\bigsqcup}(S_n\cap a\Sigma^*)$</span>. Since <span class="math-container">$S_n$</span> is infinite, there is a letter <span class="math-container">$a$</span> such that <span class="math-container">$S_n\cap a\Sigma^*$</span> is infinite. By <span class="math-container">$(P_4)$</span>, there is a letter <span class="math-container">$b$</span> distinct from <span class="math-container">$a$</span> such that <span class="math-container">$S_n\cap b\Sigma^*$</span> is non-empty. Pick <span class="math-container">$v_{n+1}\in S_n\cap b\Sigma^*$</span>. Taking <span class="math-container">$u_{n+1}$</span> to be <span class="math-container">$a$</span> would satisfy <span class="math-container">$(P_1)$</span>, <span class="math-container">$(P_2)$</span> and <span class="math-container">$(P_3)$</span> so we apply remark 3.1 to get <span class="math-container">$(P_4)$</span>: <span class="math-container">$u_{n+1}:=a\operatorname{lcp}(a^{-1}S_n)$</span>.</p>

<p><span class="math-container">$(P_1)$</span> <span class="math-container">$u_1\dots u_nv_{n+1}\in u_1\dots u_n(S_n\cap b\Sigma^*)\subseteq S$</span>.</p>

<p><span class="math-container">$(P_2)$</span> By definition of <span class="math-container">$u_{n+1}$</span> and <span class="math-container">$v_{n+1}$</span>.</p>

<p><span class="math-container">$(P_3)$</span> <span class="math-container">$a^{-1}S_n$</span> is infinite by definition of <span class="math-container">$a$</span>, and <span class="math-container">$S_{n+1}$</span> is therefore infinite by lemma 3.</p>

<p><span class="math-container">$(P_4)$</span> By definition of <span class="math-container">$u_{n+1}$</span>.</p>

<hr>

<h2>Proof of proposition 4</h2>

<p><strong>Proof of proposition 4</strong>: Let <span class="math-container">$A=(Q,\to,\Delta,q_0,F)$</span> be a NFA.</p>

<p>The idea is the following: we read <span class="math-container">$u_0$</span>, remember where we are, read <span class="math-container">$v_1$</span>, backtrack to where we were after reading <span class="math-container">$u_0$</span>, read <span class="math-container">$u_1$</span>, remember where we are, ... We also remember the first letter that was read in each <span class="math-container">$v_n$</span> to ensure that <span class="math-container">$u_n$</span> starts with another letter.</p>

<p>I've been told that this could be easier with multi-head automata but I'm not really familiar with the formalism so I'll just describe it using a Büchi automaton (with only one head).</p>

<p>We set <span class="math-container">$\Sigma':=\overline{\Sigma}\sqcup\widehat{\Sigma}$</span>, where the overlined symbols will be used to describes the <span class="math-container">$u_k$</span>s and the symbols with hats for the <span class="math-container">$v_k$</span>s.</p>

<p>We set <span class="math-container">$Q':=Q\times (\{\bot\}\sqcup (Q \times \Sigma))$</span>, where:</p>

<ul>
<li><p><span class="math-container">$(q,\bot)$</span> means that you are reading some <span class="math-container">$u_n$</span>;</p></li>
<li><p><span class="math-container">$(q,(p,a))$</span> means that you finished reading some <span class="math-container">$u_n$</span> in the state <span class="math-container">$p$</span>, that you are now reading <span class="math-container">$v_{n+1}$</span> that starts with an <span class="math-container">$a$</span>, and that once you are done, you will go back to <span class="math-container">$p$</span> to read a <span class="math-container">$u_{n+1}$</span> that does not start with <span class="math-container">$a$</span>.</p></li>
</ul>

<p>We set <span class="math-container">$q_0':=(q_0,\bot)$</span> because we start by reading <span class="math-container">$u_0$</span>.</p>

<p>We define <span class="math-container">$F'$</span> as <span class="math-container">$F\times Q \times \Sigma$</span>.</p>

<p>The set of transitions <span class="math-container">$\to'$</span> is defined as follows:</p>

<ul>
<li><p>"<span class="math-container">$u_n$</span>" For each transition <span class="math-container">$q\overset{a}{\to}q'$</span>, add <span class="math-container">$(q,\bot)\overset{\overline{a}}{\to'}(q',\bot)$</span>;</p></li>
<li><p>"<span class="math-container">$u_n$</span> to <span class="math-container">$v_{n+1}$</span>" For each transition <span class="math-container">$q\overset{a}{\to}q'$</span>, add <span class="math-container">$(q,\bot)\overset{\widehat{a}}{\to'}(q',(q,a))$</span>;</p></li>
<li><p>"<span class="math-container">$v_n$</span>" For each transition <span class="math-container">$q\overset{a}{\to}q'$</span>, add <span class="math-container">$(q,(p,a))\overset{\widehat{a}}{\to'}(q',(p,a))$</span>;</p></li>
<li><p>"<span class="math-container">$v_n$</span> to <span class="math-container">$u_n$</span>" For each transition <span class="math-container">$p\overset{a}{\to}p'$</span> where <span class="math-container">$p$</span> is final and letter <span class="math-container">$b$</span> distinct from <span class="math-container">$a$</span>, add <span class="math-container">$(q,(p,b))\overset{\overline{a}}{\to'}(p',\bot)$</span>;</p></li>
</ul>

<p><strong>Lemma 4.1</strong>: <span class="math-container">$\overline{u_0}\widehat{v_1}\overline{u_1}\widehat{v_2}\dots \overline{u_n}\widehat{v_{n+1}}$</span> is accepted by <span class="math-container">$A'$</span> iff for each <span class="math-container">$n\ge 1$</span>, <span class="math-container">$u_n$</span> and <span class="math-container">$v_n$</span> are non-empty and start with distinct letters, and for each <span class="math-container">$n\ge 0$</span>, <span class="math-container">$u_0\dots u_n v_{n+1}\in L(A)$</span>.</p>

<p><strong>Proof of lemma 4.1</strong>: Left to the reader.</p>

CC BY-SA 4.0
2019-01-08T12:53:48.733Z
2019-01-08T12:59:13.260Z
2019-01-08T12:59:13.260Z
xavierm02
<p>A set of words over a finite alphabet is <em>prefix-free</em> if there are no two distinct words where one is a prefix of the other.</p>

<p>The question is: </p>

<p><strong>What is the complexity of checking whether a regular language given as an NFA contains an infinite prefix-free subset?</strong></p>

<p><strong>Answer (due to Mikhail Rudoy, here below)</strong>: It can be done in polynomial time, and I think in even in NL. </p>

<p>Paraphrasing Mikhail's answer, let <span class="math-container">$(\Sigma,q_0,F,\delta)$</span> be the input NFA in the normal form (no epsilon transitions, trim), and let <span class="math-container">$L[p,r]$</span> (resp. <span class="math-container">$L[p,R]$</span>) be the language obtained by having state <span class="math-container">$p$</span> as initial state and <span class="math-container">$\{r\}$</span> as final state (resp. state <span class="math-container">$p$</span> as inital and the set <span class="math-container">$R$</span> as final). For a word <span class="math-container">$u$</span> let <span class="math-container">$u^\omega$</span> be the infinite word obtained by iterating <span class="math-container">$u$</span>.</p>

<p>The following are equivalent:</p>

<ol>
<li>The language <span class="math-container">$L[q_0,F]$</span> contains an infinite prefix-free subset.</li>
<li><span class="math-container">$\exists q \in Q$</span>, <span class="math-container">$\exists u \in L[q,q]\smallsetminus\{\varepsilon\}$</span> <span class="math-container">$\exists v \in L[q,F]$</span> so that <span class="math-container">$v$</span> is not a prefix of <span class="math-container">$u^\omega$</span>.</li>
<li><span class="math-container">$\exists q \in Q$</span> <span class="math-container">$L[q,q] \neq \{\varepsilon\}$</span> <span class="math-container">$\forall u \in L[q,q]$</span> <span class="math-container">$\exists v \in L[q,F]$</span> so that <span class="math-container">$v$</span> is not a prefix of <span class="math-container">$u^\omega$</span>.</li>
</ol>

<p>Proof:</p>

<p>3<span class="math-container">$\Rightarrow$</span>2 trivial.</p>

<p>For 2<span class="math-container">$\Rightarrow$</span>1, it suffices to see that for any <span class="math-container">$w \in L[q_0,q]$</span> we have that <span class="math-container">$w (u^{|v|})^* v$</span> is an infinite prefix-free subset of <span class="math-container">$L[q_0,F]$</span>.</p>

<p>Finally, 1<span class="math-container">$\Rightarrow$</span>3 is the "correctness" proof in Mikhail's answer.</p>

<fl.formal-languages><automata-theory><nfa><prefix-free-code><omega-language>
Does a given regular language contain an infinite prefix-free subset?
Googlo
# Does a given regular language contain an infinite prefix-free subset?

(Asked by: username_0 on 2018-12-27)

A set of words over a finite alphabet is *prefix-free* if there are no two distinct words where one is a prefix of the other.

The question is:

**What is the complexity of checking whether a regular language given as an NFA contains an infinite prefix-free subset?**

**Answer (due to username_1, here below)**: It can be done in polynomial time, and I think in even in NL.

Paraphrasing Mikhail's answer, let $(\Sigma,q\_0,F,\delta)$ be the input NFA in the normal form (no epsilon transitions, trim), and let $L[p,r]$ (resp. $L[p,R]$) be the language obtained by having state $p$ as initial state and $\{r\}$ as final state (resp. state $p$ as inital and the set $R$ as final). For a word $u$ let $u^\omega$ be the infinite word obtained by iterating $u$.

The following are equivalent:

1. The language $L[q\_0,F]$ contains an infinite prefix-free subset.
2. $\exists q \in Q$, $\exists u \in L[q,q]\smallsetminus\{\varepsilon\}$ $\exists v \in L[q,F]$ so that $v$ is not a prefix of $u^\omega$.
3. $\exists q \in Q$ $L[q,q] \neq \{\varepsilon\}$ $\forall u \in L[q,q]$ $\exists v \in L[q,F]$ so that $v$ is not a prefix of $u^\omega$.

Proof:

3$\Rightarrow$2 trivial.

For 2$\Rightarrow$1, it suffices to see that for any $w \in L[q\_0,q]$ we have that $w (u^{|v|})^\* v$ is an infinite prefix-free subset of $L[q\_0,F]$.

Finally, 1$\Rightarrow$3 is the "correctness" proof in Mikhail's answer.

**Tags:** fl.formal-languages, automata-theory, nfa, prefix-free-code, omega-language


---

## 2 answers

### Answer by username_1 on 2018-12-27. Score: 8 | Accepted answer

Your problem can be solved in polynomial time.

To begin, convert the given NFA to an equivalent NFA with the following additional properties:

* There are no epsilon transitions
* All states are reachable from the start state

## Helpful subroutine

Suppose we have an NFA $N$, a state $q$, and a nonempty string $s$. The following subroutine will let us evaluate the truth value of the following statement: "every path in $N$ from state $q$ to an accept state corresponds to a string that is a prefix of string $s^n$ for some $n$." Furthermore, this subroutine will run in polynomial time.

First, construct the NFA $S$ with $|s| + 1$ states which accepts all strings that are not prefixes of $s^n$ for any $n$ ($|s|$ non-accept states in a loop to keep track of where in the "pattern" of $sssss\ldots$ we are so far, and one accept state for if we have already deviated from that pattern). Next, construct the NFA $N'$ which is exactly like $N$ but has $q$ as its start state. Finally, construct a final NFA $N''$ whose language $L(N'')$ is $L(S) \cap L(N')$ using the standard NFA intersection construction. Note that all of these constructions are polynomial in the size of the input.

Then simply test whether the language of $N''$ is empty (which can be done in polynomial time with a simple graph search). $L(N'') = \emptyset$ if and only if $L(S) \cap L(N') = \emptyset$, or in other words every string in $L(N')$ is not in $L(S)$. In other words, the language of $N''$ is empty if and only if $N'$ accepts only strings that are prefixes of $s^n$ for some $n$. This can be rephrased as exactly the statement we were trying to evaluate: "every path in $N$ from state $q$ to an accept state corresponds to a string that is a prefix of string $s^n$ for some $n$."

## Main algorithm

Consider the set of states in the NFA that are in some loop. For each such state, $q$, do the following:

Let $P\_2$ be any simple loop containing $q$. Let $s$ be the string corresponding to loop $P\_2$. Since the NFA has no epsilon transitions, $s$ is not empty. Then apply the subroutine to the NFA, state $q$, and string $s$. If the subroutine tells us that every path starting at $q$ in the NFA and ending at an accept state corresponds to a prefix of $s^n$ for some $n$ then continue to the next state $q$. Otherwise, output that the given NFA's language contains an infinite prefex-free subset.

If we try every state $q$ that is in a loop and the algorithm never outputs, then output that the given NFA's language does not contain an infinite prefex-free subset.

## Correctness (first half)

First, suppose that the above algorithm asserts that the given NFA's language contains an infinite prefex-free subset. Let's say that this output was selected while considering some loop $P\_2$ and some state $q$. As before, $s$ is the string corresponding to $P\_2$. Then we know according to the subroutine that not every path starting at $q$ in the NFA and ending at an accept state corresponds to a prefix of $s^n$ for some $n$ (as this is the only output of the subroutine that would lead to the main algorithm outputting at that $q$).

Let $P\_3$ be a path whose existence is asserted by the subroutine: a path from $q$ to an accept state such that the corresponding string $t$ is not a prefix of $s^n$ for any $n$.

Let $P\_2'$ consist of $m$ copies of $P\_2$ where $m$ is sufficiently large that $m|s| > |t|$. Since $P\_2$ is a loop through $q$, $P\_2'$ can be treated as a path from $q$ to $q$. The string corresponding to $P\_2'$ is $s^m$

Let $P\_1$ be a path from the start state to $q$ (which exists since every state is reachable from the start) and let $r$ be the string corresponding to this path.

Then the path consisting of $P\_1$, $x$ copies of $P\_2'$, and $P\_3$ is an accepting computation path. The string corresponding to this path is $r(s^m)^xt$. Thus, the NFA accepts every string of the form $r(s^m)^xt$. This is an infinite set of strings accepted by the NFA, and I claim that this set of strings is prefix-free. In particular, suppose $r(s^m)^xt$ is a prefix of $r(s^m)^yt$ with $y > x$. In other words, $t$ is a prefix of $(s^m)^{y-x}t$. Since $(s^m)^{y-x}$ has length $m(y-x)|s| \ge m|s| > |t|$, this implies that $t$ is a prefix of $(s^m)^{y-x} = s^{m(y-x)}$. But we know by the output of the subroutine that $t$ is not a prefix of $s^n$ for any $n$. Thus, $r(s^m)^xt$ cannot be a prefix of $r(s^m)^yt$, and as desired the set of strings is prefix-free.

Thus, I have shown that if the main algorithm outputs that the given NFA's language contains an infinite prefex-free subset then this is in fact the case.

## Correctness (second half)

Next, I will show the other half: if the given NFA's language contains an infinite prefex-free subset then the main algorithm will output this fact.

Suppose the given NFA's language contains an infinite prefix-free subset. Let $A$ be the set of (accepting) computation paths corresponding to these strings. Notice that $A$ is an infinite set of accepting computation paths whose corresponding strings are never prefixes of each other.

Say that a state is "looping" in the NFA if there exists a loop in the NFA through that state and "non-looping" otherwise. Consider all paths from the start state to any looping state which pass through only non-looping states (except for the one looping state where they end up). Let $P$ be the set of these paths. Each path $p \in P$ cannot have a loop as then the states in that loop would be looping states and so $p$ would pass through a looping state. Thus, the lengths of paths in $P$ are bounded above by the number of states in the NFA and so $P$ is finite (for example, if the start state is a looping state then the only such path is the empty path).

We can partition $A$ into $|P|+1$ subsets based on how that computation paths in $A$ starts. In particular, for $p \in P$, let $A\_p$ be the set of all computation paths in $A$ that start with path $p$ and let $B$ be the set of all other paths in $A$. Clearly, all $A\_p$s and $B$ are disjoint and their union is the entire set $A$. Furthermore, $B$ contains only paths that never pass through a looping state, and therefore never loop; thus $B$ is finite. We can conclude then that some $A\_p$ must be infinite (otherwise $A$ would be a union of finitely many finite sets).

Since $A\_p$ is infinite, there are infinitely many computation paths, none of whose strings are prefixes of each other, that are accepting paths starting with $p$. Let $q$ be the state reached at the end of path $p$. We can conclude that there are infinitely many accepting paths, call this set $A'$, starting at $q$ all of which correspond to strings that are not prefixes of each other.

During the main algorithm, we run the subroutine on state $q$ and some string $s$. This subroutine tells us whether every accepting path starting at $q$ corresponds to a string that is a prefix of $s^n$ for some $n$. If this were the case, then all the infinitely many accepting paths in $A'$ would be prefixes of $s^n$ for various $n$, which would imply that they are all prefixes of each other. This is not the case, so we conclude that when the main algorithm runs the subroutine on state $q$, the result is the other possible outcome. This, however, leads the main algorithm to output that the NFA's language contains an infinite prefix-free subset.

This concludes the proof of correctness.

> **Comments:**
> **username_2**: I don't understand how the loop handling works, since a given state $q$ can be part of (exponentially) many loops. Of course, if any two of those loops can be used to generate a non-periodic sequence, then we are done.  
> **username_1**: What do you mean by loop handling? In the main algorithm, for each state $q$ you pick just one loop that goes through $q$ (any loop out of the potentially exponentially many) and call that loop $P_2$ (afterwords you run the subroutine on state $q$ and string $s$ where $s$ is the string associated with $P_2$). The subroutine essentially handles the check of whether it is possible to generate a non-periodic sequence using that loop. If yes, then we're done. If no (and furthermore no for every $q$), then your entire language is a union of periodic sequences so we're also done.  
> **username_2**: To make my question clearer, here's a simple NFA with initial state $q$, final state $T$ and three transitions: $q \overset{a}{\rightarrow} q$, $q \overset{b}{\rightarrow} q$, $q \overset{a}{\rightarrow} T$. The loop for $a$ will not generate the prefix-free strings, but the loop for $b$ will.  
> **username_1**: Actually, the loop for $a$ does generate a prefix free set: the set of strings $a^*ba$ all use the $a$ loop. In my algorithm, if the loop you choose for $q$ is the $a$ loop then the subroutine will determine that no, not every accepting path starting at $q$ has a string of the form $a^*$, and so the main algorithm will say that an infinite prefix-free subset exists. If the loop the algorithm uses for $q$ is instead the $b$ loop then the subroutine determines that not every accepting path starting at $q$ has a string of the form $b^*$, and in this case too the algorithm has the same output.  
> **username_0**: Thank you Mikhail! I think your answer settles the question.  

---

### Answer by username_3 on 2019-01-08. Score: 2

Definitions
Definition 1: Let $S$ be a set of words. We say that $S$ is nicely infinite prefix-free (made up name for the purpose of this answer) if there are words $u_0,\dots,u_n,\dots $ and $v_1,\dots,v_n,\dots $ such that:

For each $n\ge 1$, $u_n$ and $v_n$ are non-empty and start with distinct letters;
$S=\{u_0v_1,\dots,u_0\dots u_n v_{n+1},\dots\}$.

The intuition is that you can put all those words on an infinite rooted tree (the ■ is the root, the ▲ are the leaves, and the • are the remaining interior nodes) of the following shape such that the words in $S$ are exactly the labels of paths from the root to a leaf:
   u₀    u₁    u₂
■-----•-----•-----•⋅⋅⋅
      |     |     |
      | v₁  | v₂  | v₃
      |     |     |
      ▲     ▲     ▲

Proposition 1.1: A nicely infinite prefix-free set is prefix-free.
Proof of proposition 1.1: Suppose that $u_0\dots u_n v_{n+1}$ is a strict prefix of $u_0 \dots u_m v_{m+1}$. There are two cases:

If $n < m$ then $v_{n+1}$ is a prefix of $u_{n+1}\dots u_m v_{m+1}$. This is impossible because $u_{n+1}$ and $v_{n+1}$ have distinct first letters.
If $n > m$ then $u_{m+1}\dots u_n v_{n+1}$ is a prefix of $v_{m+1}$. This is impossible because $u_{m+1}$ and $v_{m+1}$ have distinct first letters.

Proposition 1.2: A nicely infinite prefix-free set is infinite.
Proof of proposition 1.2: In proof 1.1, we showed that if $n\not= m$ then $u_0\dots u_n v_{n+1}$ and $u_0 \dots u_m v_{m+1}$ are not comparable for the prefix order. They are therefore not equal.

Main proof
Proposition 2: Any infinite prefix-free set contains a nice infinite prefix-free set.
Proposition 3: A language contains an infinite prefix-free set if and only if it contains a nicely infinite prefix-free set.
Proof below.
Proof of proposition 3: $\boxed{\Rightarrow}$ by proposition 2. $\boxed{\Leftarrow}$ by propositions 1.1 and 1.2.
Proposition 4: The set of nicely-prefix-free subsets of a regular language (encoded as an infinite word $\overline{u_0}\widehat{v_1}\overline{u_1}\widehat{v_2}\overline{u_2}\dots$) is $\omega$-regular (and the size of the Büchi automaton recognizing it is polynomial in the size of the NFA recognizing the regular language).
Proof below.
Theorem 5: Deciding if a regular language described by a NFA contains an infinite prefix-free subset can be done in time polynomial in the size of the NFA.
Proof of theorem 5: By proposition 3, it is sufficient to test if it contains a nicely-infinite prefix-free subset, which can be done in polynomial time by building the Büchi automaton given by proposition 4 and testing the non-emptyness of its language (which can be done in time linear in the size of the Büchi automaton).

Proof of proposition 2
Lemma 2.1: If $S$ is a prefix-free set, then so is $w^{-1}S$ (for any word $w$).
Proof 2.1: By definition.
Lemma 2.2: Let $S$ be an infinite set of words. Let $w:=\operatorname{lcp}(S_n)$ be the longest prefix common to all words in $S$. $S$ and $w^{-1}S$ have the same cardinal.
Proof 2.2: Define $f:w^{-1}S\to S$ by $f(x)=wx$. It is well defined by definition of $w^{-1}S$, injective by definition of $f$ and surjective by definition of $w$.
Proof of proposition 2: We build $u_n$ and $v_n$ by induction on $n$, with the induction hypothesis $H_n$ composed of the following parts:

$(P_1)$ For all $k\in\{1,\dots,n\}$, $u_0\dots u_{k-1} v_k \in S$;
$(P_2)$ For all $k\in\{1,\dots,n\}$, $u_k$ and $v_k$ are non-empty and start with distinct letters;
$(P_3)$ $S_n:=(u_0\dots u_n)^{-1}S$ is infinite;
$(P_4)$ There is no non-empty prefix common to all words in $S_n$. In other words: There is no letter $a$ such that $S_n\subseteq a\Sigma^*$.

Remark 2.3: If we have sequences that verify $H_n$ without $(P_4)$, we can modify $u_n$ to make them to also satisfy $(P_4)$. Indeed, it suffices to replace $u_n$ by $u_n\operatorname{lcp}(S_n)$. $(P_1)$ is unaffected. $(P_2)$ is trivial. $(P_4)$ is by construction. $(P_3)$ is by lemma 3.
We now build the sequences by induction on $n$:

Initialization: $H_0$ is true by taking $u_0:=\operatorname{lcp}(S)$ (i.e. by taking $u_0:=\varepsilon$ and applying remark 3.1).
Induction step: Suppose that we have words $u_1,\dots,u_n$ and $v_1,\dots,v_n$ such that $H_n$ for some $n$. We will build $u_{n+1}$ and $v_{n+1}$ such that $H_{n+1}$.

Since $S_n$ is infinite and prefix-free (by lemma 1), it does not contain $\varepsilon$ so that $S_n=\underset{a\in \Sigma}{\bigsqcup}(S_n\cap a\Sigma^*)$. Since $S_n$ is infinite, there is a letter $a$ such that $S_n\cap a\Sigma^*$ is infinite. By $(P_4)$, there is a letter $b$ distinct from $a$ such that $S_n\cap b\Sigma^*$ is non-empty. Pick $v_{n+1}\in S_n\cap b\Sigma^*$. Taking $u_{n+1}$ to be $a$ would satisfy $(P_1)$, $(P_2)$ and $(P_3)$ so we apply remark 3.1 to get $(P_4)$: $u_{n+1}:=a\operatorname{lcp}(a^{-1}S_n)$.
$(P_1)$ $u_1\dots u_nv_{n+1}\in u_1\dots u_n(S_n\cap b\Sigma^*)\subseteq S$.
$(P_2)$ By definition of $u_{n+1}$ and $v_{n+1}$.
$(P_3)$ $a^{-1}S_n$ is infinite by definition of $a$, and $S_{n+1}$ is therefore infinite by lemma 3.
$(P_4)$ By definition of $u_{n+1}$.

Proof of proposition 4
Proof of proposition 4: Let $A=(Q,\to,\Delta,q_0,F)$ be a NFA.
The idea is the following: we read $u_0$, remember where we are, read $v_1$, backtrack to where we were after reading $u_0$, read $u_1$, remember where we are, ... We also remember the first letter that was read in each $v_n$ to ensure that $u_n$ starts with another letter.
I've been told that this could be easier with multi-head automata but I'm not really familiar with the formalism so I'll just describe it using a Büchi automaton (with only one head).
We set $\Sigma':=\overline{\Sigma}\sqcup\widehat{\Sigma}$, where the overlined symbols will be used to describes the $u_k$s and the symbols with hats for the $v_k$s.
We set $Q':=Q\times (\{\bot\}\sqcup (Q \times \Sigma))$, where:

$(q,\bot)$ means that you are reading some $u_n$;
$(q,(p,a))$ means that you finished reading some $u_n$ in the state $p$, that you are now reading $v_{n+1}$ that starts with an $a$, and that once you are done, you will go back to $p$ to read a $u_{n+1}$ that does not start with $a$.

We set $q_0':=(q_0,\bot)$ because we start by reading $u_0$.
We define $F'$ as $F\times Q \times \Sigma$.
The set of transitions $\to'$ is defined as follows:

"$u_n$" For each transition $q\overset{a}{\to}q'$, add $(q,\bot)\overset{\overline{a}}{\to'}(q',\bot)$;
"$u_n$ to $v_{n+1}$" For each transition $q\overset{a}{\to}q'$, add $(q,\bot)\overset{\widehat{a}}{\to'}(q',(q,a))$;
"$v_n$" For each transition $q\overset{a}{\to}q'$, add $(q,(p,a))\overset{\widehat{a}}{\to'}(q',(p,a))$;
"$v_n$ to $u_n$" For each transition $p\overset{a}{\to}p'$ where $p$ is final and letter $b$ distinct from $a$, add $(q,(p,b))\overset{\overline{a}}{\to'}(p',\bot)$;

Lemma 4.1: $\overline{u_0}\widehat{v_1}\overline{u_1}\widehat{v_2}\dots \overline{u_n}\widehat{v_{n+1}}$ is accepted by $A'$ iff for each $n\ge 1$, $u_n$ and $v_n$ are non-empty and start with distinct letters, and for each $n\ge 0$, $u_0\dots u_n v_{n+1}\in L(A)$.
Proof of lemma 4.1: Left to the reader.


---

