A key problem in software testing is having the right cost/benefit tradeoffs for the software that is being tested. Based on the 2-8 law of fault distribution in programs, the paper divides the test process in two stages for solving this problem. The first stage is to find the faults in software at minimum cost, and the second stage is to add some additional test cases for those faults found in the first stage to detect more potential faults in software. The paper lays emphasis on the realization of the first stage. According to the theories of both the deterministic finite state machine (DFSM) and set partition, a DFSM-based minimum test cost transition coverage criterion is presented in this paper, and the criterion’s sufficiency and necessary conditions are given. Moreover, two algorithms that realize the optimal transition coverage and the minimum test cost transition coverage are designed, and the effectiveness of the test set is also discussed. In the experiments, the method not only obtains a set of test cases with the minimal size and the shortest total length of all test cases, but also finds all faults in transitions of the DFSM.