New answers tagged automata-theory
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 ...
- 691
9
votes
Error in Robson's proof about separating strings?
Thanks Tassle. I was about to give the same answer.
J.M. Robson.
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:
...
- 1,310
Top 50 recent answers are included