5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Perhaps it is. Here's what I mean (maybe you can help reword it?): is there some length of string that for all strings of that length, $R$ accepts them? So it may not accept all the strings of length 1, but it does accept all strings of length 2. ex. $(aa|ab|ba|bb)^*$ accepts all strings of length that are multiples of 2, so the answer would be "yes". $\endgroup$ – Chill Mar 28 '13 at 20:25
  • 1
    $\begingroup$ after reading the question more carefully I see that it is correct (a complementary way to formulate it is: does R reject at least one string of length $l$ for all $l \geq 1$). I delete my comment above. $\endgroup$ – Vor Mar 28 '13 at 20:31
  • $\begingroup$ I hadn't thought of tackling it using the complement. I'm going to play around with that for a bit and see if I can get somewhere. $\endgroup$ – Chill Mar 28 '13 at 20:34
  • $\begingroup$ think about it in unary ... let me know if you need further help :-) $\endgroup$ – Vor Mar 28 '13 at 20:41
  • $\begingroup$ Well, of course it is decidable for unary (answer yes unless it accepts no strings at all), but the problem really is meant for alphabets with more than one letter. $\endgroup$ – Chill Mar 28 '13 at 20:51
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'll need to give this some more thought. It seems correct, but I'm not 100% convinced that when the set of states reached by all strings of length $k$ is the same as some previous set of states, we get to terminate. $\endgroup$ – Chill Mar 28 '13 at 21:20
  • $\begingroup$ @Chill I think it's true for the following reason: the set of states reachable in $k+1$ steps from the start state is the same as the set of states reachable in 1 step from $S_k$. Call $S_0 = \{q_0\}$. Define a function $f(X)$ to be the set of states reachable from states in $X$ in one step. Then if $X = Y$, $f(X) = f(Y)$. Therefore, if $S_k = S_{k'}$, the sets of states reachable in one step from $S_k$ and $S_{k'}$ - $S_{k+1}$ and $S_{k'+1}$ - should be the same, too... but think on it some more, and let me know if still think it's suspect. $\endgroup$ – Patrick87 Mar 28 '13 at 21:30
  • $\begingroup$ I keep going back and forth between "it works" and "it doesn't". Here's my most convincing argument of why it works so far. We can easily modify the DFA to have a single accept state $q_f$. Consider the case when $S_k = q_f$. The previous set of states, $S_{k-1}$ must, for all input, transition to $q_f$. Use inductive reasoning, and we must conclude that every single set of states from the algorithm must be unique (or else it terminates). $\endgroup$ – Chill Mar 28 '13 at 23:53
  • $\begingroup$ @Chill Is there any reason in particular you think it doesn't work? I'm not sure you need the DFA to have a single accepting state; in fact, the reasoning used doesn't even seem to require a DFA at all (i.e., an NFA would work). If there's anything I could add to the answer to help clarify the approach, please let me know. $\endgroup$ – Patrick87 Mar 29 '13 at 13:16
  • $\begingroup$ I'm convinced it is correct now. Thanks for your answer :). $\endgroup$ – Chill Mar 29 '13 at 15:10
1
$\begingroup$

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}$.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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