The motivation for this question is the fact that partitioning DFA into equivalence classes is the mechanism that is used in model testing to generate test cases. However, obviously, DFA cannot describe arbitrary programs.

Perhaps DFA can be extended (w/o becoming fullblown PDA), while still having the property that it can be paritioned into equivalence classes?

This question is, in part, based on my reading of Model-Based Testing of Reactive Systems, which spends most of its time talking about DFAs.

  • $\begingroup$ Perhaps you should start with NFAs before you think about PDAs. $\endgroup$ – Yuval Filmus Oct 8 '18 at 4:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.