New answers tagged

7 votes
Accepted

Error in Robson's proof about separating strings?

Converting my comment to an answer: This is taken care of in the paragraph just before Theorem 1. If the accepting state is reached at some $v_j$, then we necessarily have $j>i$, and we can compose ...
Tassle's user avatar
  • 691
9 votes

Error in Robson's proof about separating strings?

Thanks Tassle. I was about to give the same answer. J.M. Robson.
John Michael Robson's user avatar
5 votes
Accepted

Deciding finiteness of regular language is NL-complete?

Let $\mathcal{A}$ be an NFA. We say that a state $q$ lies on a cycle if there is a non-empty path from $q$ to $q$ in the graph of $\mathcal{A}$. In my answer I assume that the following lemma is true: ...
Bartosz Bednarczyk's user avatar

Top 50 recent answers are included