$ALL_{REGEX}$ is the computational problem of determining for regular expression x if $L(x) = \Sigma^*$. In a proof for $ALL_{REGEX} \in PSPACE$, the following non-deterministic turing machine $M(R)$ on regular expression $R$ is given

Convert R to an NFA $N = (Q,\Sigma,\delta,S,F)$; $K = S$;

While $K \cap F \neq \emptyset$

  1. Non-deterministically guess a character $a \in \Sigma$
  2. S' = Compute the new set of states from character $a$ and states $K$
  3. K = S'

The proof states that iff $M$ does not halt, then $L(R) = \Sigma^*$. Suppose we have $\Sigma = \{a,b\}$ and R = a*. Why doesn't this machine halt? Won't there be a single path of guesses (namely, a*) that goes on forever, implying the whole machine does as well?

The algorithm goes prove that after $2^{|Q|}$ steps, we know the language must be $\Sigma^*$, so we accept instead of looping. I understand the intuition of the algorithm and how it would be implemented deterministically , but I'm confused as to how the algorithm above works when the NTM formalism accepts if any path accepts and it is making me question my understanding of NTMs.

  • $\begingroup$ @DavidRicherby - see edits $\endgroup$ – dfb Mar 12 '14 at 17:50

The idea is that if a DFA having $n$ states isn't universal (doesn't accept $\Sigma^*$) then there must be some word of length at most $n$ which it doesn't accept. The proof is similar to the proof of the pumping lemma: take any word not accepted by the DFA, and trace its route through the DFA. You can always shorten it to a word which ends up in the same state, and additionally all states encountered are distinct. Since there are only $n$ distinct states, this finished up the proof.

An NFA having $n$ states is equivalent, via the powerset construction, to a DFA having $2^n$ states. Therefore if it is not universal then it rejects some word of length at most $2^n$. The non-deterministic algorithm you describe guesses such a word and verifies that it is indeed rejected by the NFA. Since NPSPACE=PSPACE, we can convert this into a deterministic algorithm (in fact, one using space $O(n^2)$).

| cite | improve this answer | |
  • $\begingroup$ I understand the logic of the proof you describe. The way I read it, though, the algorithm guesses every word and accepts if at least one word has the critical length. How does it verify that at least one word is rejected in the algorithm above? $\endgroup$ – dfb Mar 12 '14 at 17:59
  • $\begingroup$ My proof is the same as the one you give. The algorithm accepts if for some sequence of guesses, it terminates. In this case, we know that the NFA isn't universal, since we have reached a state in the simulated DFA which is not accepting. If for all sequences of guesses the algorithm never terminates, then the NFA is universal. $\endgroup$ – Yuval Filmus Mar 12 '14 at 19:26
  • $\begingroup$ Yep, understood - I'm hung up on the NTM formalism in regards to the last statement - "If for all sequences of guesses the algorithm never terminates, then the NFA is universal". The algorithm in my post fails to terminates if any computational path loops, not all of them, right? e.g., R=a*, sigma = {a,b} never terminates $\endgroup$ – dfb Mar 12 '14 at 19:37
  • $\begingroup$ It depends on the semantics of the nondeterministic Turing machine. The correct semantics here is whatever makes my argument work, that is, the machine accepts if some path terminates. Compare that with your interpretation: it accepts if all paths terminate. Nondeterminism machines have an exists quantifier, while a for all quantifier appears in co-nondeterministic machines. $\endgroup$ – Yuval Filmus Mar 13 '14 at 2:04

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.