Pseudoexhaustive testing of a combinational circuit involves applying all possible input patterns to all its individual output cones. Since it does not assume any fault model, the testing ensures detection of all static detectable faults in the circuit that do not require two-pattern tests. Earlier works on pseudoexhaustive testing usually genereate test sets that are several orders of magnitude larger than the minimum size test set required for a specific circuit, and are mostly based on LFSRs. This paper presents a novel strategy for constructing circuit-specific pseudoexhaustive test pattern generators based on cellular automata that results in generating minimal pseudoexhaustive test sets for combinational circuits. Experimentation with ISCAS85 benchmarks show that as compared to the LFSRs, Cellular Automata based approach often results in simpler circuitry with lesser number of shift stages and reduced test length. Moreover, the analytical technique developed here is generic in nature and thus can as well be applied for constructing LFSR based pseudoexhaustive test pattern generators. Index Terms: Test pattern generators, pseudoexhaustive testing, cellular automata.