1
$\begingroup$

I have to construct a DFA which ends with aa and does not contain any pair of b-s. A = {a,b}, {aa,baa,aaa,abaa,babaa,...}. I know how to construct them as separate DFAs but not together merged.

$\endgroup$
2
$\begingroup$

If you know how to construct DFAs for two languages separately, you can use systematic methods to build the DFA which recognises the intersection of the languages (e.g. https://math.stackexchange.com/questions/147457/intersection-of-two-deterministic-finite-automata). However to achieve a minimalist and elegant result (as well as for learning purposes) you may want to try and find ad-hoc methods. NB: You can always apply a DFA minimization procedure to 'clean up' the automaton obtained via the above general method (https://en.m.wikipedia.org/wiki/DFA_minimization).

$\endgroup$
2
  • $\begingroup$ Once you have any DFA implementing the desired behavior, you can create a minimal DFA from it via any of the well-known DFA minimization methods. This does not require any ad-hoc reasoning, and the computational cost is tiny for DFAs this small. $\endgroup$ Jan 15 '20 at 22:19
  • $\begingroup$ Yes you are right, my comment on minimality isn't really relevant. Still I think that it can be instructive to try and build a DFA from scratch, in preparation for the day where the DFA is too large. $\endgroup$
    – integrator
    Jan 16 '20 at 1:49

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.