[gliptic]

NFAs are decidable. As you said, a NFA can be converted to a DFA which is decidable. Maybe you mean they are non-deterministic (that's in the name)?

[banish-m4]

You know what I meant. I used the wrong word.