ABSTRACT
We show the following three problems are NP complete.
Given finite sets X and Y of words, determine if there is a 2 state finite automaton accepting X and rejecting Y.
Given a word x and a finite set of words Y, determine if there is a 4 state finite automaton accepting x and rejecting Y.
Given finite sets X and Y of words on a 4 letter alphabet and an integer k, determine if there is a k state finite automation accepting X and rejecting Y.
