Can a Turing Machine decide if a regular expression matches all strings of exactly some length $l \geq 1$?

Question

Earlier I asked the question: Can a Turing Machine decide if an NFA accepts a string of prime length?. The answer introduced me to Parikh's theorem, which I've been reading about. The concept of Parikh's theorem, if we apply it to regular expressions, allows us to break down a regular expression into expressions that only have one level of Kleene-star nesting.

So: $aa(b(cc)^*)^*$ can have a list of expressions created using the same methodology as Parikh's theorem where none of the new expressions in the final list has nested Kleene-stars. The linear subsets will use starred expressions

To make it more clear, I'm referencing this paper: http://people.inf.ethz.ch/torabidm/par-ext.pdf.

I'm not too concerned with it actually being a regular expression, DFAs or NFAs would work fine. It seems easier to work with as an RE.

---

I want to know if the problem is decidable:

Instance: A regular expression $R$

Question: Does there exist some length $l \ge 1$ such that $R$ accepts every string of that length (ie. if its alphabet is $\Sigma$, it accepts $\Sigma^l$, for some $l \ge 1$.

---

I'm pretty sure the problem actually is decidable but it's a tough one. I've enjoyed pondering it so far and would love to see what someone more experienced than myself can come up with.

Answer 1

I think this procedure should work...

First, construct a DFA for the language. Now, start tracing all possible paths of length $k$ (start with $k = 1$). Call $S_k$ the set of states reached by strings of length $k$.

If at any point you find $S_k \subseteq A$, the set of accepting states, the answer is yes, and return.

If, on the other hand, you find that $S_{k} = S_{k'}$, where $k' < k$, before you find an $S_k$ that works, you know that you'll never find an $S_k$ that works, and you can stop looking. The reason is that the next length you try, $k + 1$, will yield $S_{k+1} = S_{k'+1}$, another set that didn't work... and so on.

Note that this procedure is guaranteed to terminate since there are a finite number of possible $S_k$; since they're subsets of the set of all states, $S$, there are no more than $2^{|S|}$ of them. By the pigeonhole principle, if you've tried enough candidates, you'll either have already found one that worked, or you'll have tried some set more than once.

Apologies in advance if this is completely missing the point of the question, blatantly wrong or intellectually hilarious.

Answer 2

While the algorithm above is fine, it may use exponential space, while this problem for DFAs should be polynomial time equivalent to (the complement of) the universality problem for NFAs. This makes it PSPACE-complete (according to this answer: https://mathoverflow.net/questions/24343/emptiness-and-determinization-of-nfas/24422#24422). The problem here for regular expressions or NFAs might be even harder, since a minimal DFA might have exponentially many states.

---

This problem for DFAs $\leq^p \overline{\mathrm{NFA-UNIV}}$:

Given a DFA $M$ with alphabet $\Sigma$, first compute $\overline{M}$ (DFA for $\overline{L(M)}$) by switching final and non final states, let $\delta$ be its transition function. Now construct an NFA $N$ with the same states, alphabet $\{a\}$ and transition function $\delta'$ s.t.

$$ \delta'(z,a) = \{z' \mid \exists b: \delta(z,b) = z'\}$$

If $N$ accepts a word $a^l$ then $\overline{M}$ accepts a word of length $l$ and $M$ does not accept all words of length $l$. So there is an $l$ s.t. $M$ accepts all words of length $l$ if and only if $L(N)\neq\{a\}^*$.

---

$\overline{\mathrm{NFA-UNIV}} \leq^p $ this problem for DFAs:

For the other direction we use the same names but the construction is carried out in the opposite way. W.l.o.g. we assume $N$ has only one initial state. Let $\Sigma$ be the alphabet of $N$ and $k$ maximal s.t. $\exists z,a: k = |\delta'(z,a)|$. The alphabet of $\overline{M}$ is now $\Sigma \times \{1,\dots,k\}$ and if $\delta'(z,a) = \{z_{i_1},\dots,z_{i_m}\}$ we define $$\delta(z,(a,j))=\begin{cases}z_{i_j}&j\leq m \\ E & \text{else}\end{cases}$$ where $E$ is some special new error state (i.e. non final and $\forall a: \delta(E,a)=E$). Now a path form the initial state to a final state in $N$ maps to such a path in $\overline{M}$ (and vice versa). Finally we define $M$ by switching final and non final states of $\overline{M}$.

Answer 3

This can be solved using closure properties of regular languages and uniqueness of the minimal DFA.

Proceed as follows:

• Construct an NFA for the given regular expression.
• Construct the canonical DFA for $\Sigma^l$ (a linear chain with $l+1$ states, maybe an additional error state).
• Intersect the two (standard algorithm).
• Determinise and minimise.

If and only if $\mathcal{L}(R) \supseteq \Sigma^l$ the resulting automaton equals the one for $\Sigma^l$ (up to state names).