This paper addresses the issue of identifying a Cellular Automaton able to generate deterministic input patterns to detect stuck-at faults inside an FSM. A suitable hardware structure is first identified. An evolutionary algorithm is then proposed, which directly identifies a Cellular Automaton able to reach a very good Fault Coverage. The novelty of the method consists in combining the generation of test patterns with the synthesis of a Cellular Automaton able to reproduce them. Experimental results are provided, which show that the proposed hardware architecture and algorithmic approach outperform more traditional solutions, based on ATPG tools and FSM synthesis, from the point of view of both applicability and area occupation, while reaching the same Fault Coverage.