how NFA implement negate regex

Question

I try to use NFA to implement a negate regex.

I know that NFA can easily combine regex like ab a|b and a*

and the variety [ab] can convert to a|b

but how can I convert [^ab] to a NFA fragment?

Answer 1

This is just a character class. The transitions of NFAs are labeled with single characters or lambda (the empty string). To implement a character class, just have a transition for each character in the class. The negated class is just implemented with one transition for each character not in the class. Since the NFA is required to have a finite alphabet, this is no problem at all. If A is the alphabet and you want [^ab], then you need one transition for each character in the set A - {a, b}.