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

Problem Detail: 

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.

Asked By : Chill

Answered By : Patrick87

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10879