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 ...
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:
...
Top 50 recent answers are included
Related Tags
automata-theory × 417fl.formal-languages × 188
regular-language × 79
reference-request × 61
cc.complexity-theory × 42
dfa × 40
context-free × 32
computability × 26
turing-machines × 26
regular-expressions × 22
lo.logic × 21
grammars × 21
ds.algorithms × 17
omega-language × 17
nondeterminism × 14
co.combinatorics × 13
graph-theory × 12
minimization × 12
nfa × 10
algebra × 9
time-complexity × 8
model-checking × 8
probabilistic-automata × 8
graph-algorithms × 7
lower-bounds × 7