0
$\begingroup$

Exactly as the title says, I'm looking for a DFA for an even number of A, odd number of B, and exactly one C, can anyone help with this?

Thanks

$\endgroup$
  • $\begingroup$ Does every string contain (an even number of A) AND (an odd number of B) AND (exactly one C)"? Or does your language contain strings with an even number of A, odd number of B, exactly one C? $\endgroup$ – fade2black Nov 20 '17 at 16:29
  • $\begingroup$ Possible words include BC, CB, ABCA, BBACBA. Words that aren't in the language are: B, A, ABBA, ACABB. So it doesn't have to require A AND B $\endgroup$ – user103296 Nov 20 '17 at 16:40
  • $\begingroup$ According to your examples it looks like every string contain an even number of A AND an odd number of B AND exactly one C. $\endgroup$ – fade2black Nov 20 '17 at 17:11
1
$\begingroup$

Divide and conquer. You could design a DFA over the alphabet $\Sigma = \{A,B,C\}$

  • for an even number of A, call it $M_1$
  • for an odd number of B, call it $M_2$
  • accepting exactly one C, call it $M_3$

Then design a new DFA equivalent to $M_1 \cap M_2 \cap M_3$ (by closure properties of regular languages).

$\endgroup$
  • $\begingroup$ In the language are CB, ABCA, BBACBA. Using ∩ wouldn't allow this would it? $\endgroup$ – user103296 Nov 20 '17 at 15:53
  • $\begingroup$ @user103296 Yes, the intersection accepts these strings strings. $\endgroup$ – fade2black Nov 20 '17 at 16:55
0
$\begingroup$

A common idiom for problems like this is to use the states to remember what has been seen so far: are there an even number of A's or not; are there an even number of B's or not; are there 0, 1, 2 or more C's?

For example, having seen the input ABAABCA, we would be in state (even A's, even B's, 1 C) and then if we see an A we would pass to state (odd A's, even B's, 1 C). I'll leave it to you to determine which of the twelve states should be the start and which should be the final state.

$\endgroup$
  • $\begingroup$ That makes sense thank you, do you possibly know how I would be able to turn my problem into a regular expression in order to make an NFA? $\endgroup$ – user103296 Nov 20 '17 at 16:33
  • $\begingroup$ @user103296 The question asks about making DFA. Why are you then asking about regular expressions? Regular expressions (Type-3 grammar) are much more restrictive than those which can be processed by a DFA (Type-0 grammars) $\endgroup$ – Cort Ammon - Reinstate Monica Nov 20 '17 at 16:41
  • $\begingroup$ I was taught to start with a regular expression, then make a NFA, then convert that to a DFA. $\endgroup$ – user103296 Nov 20 '17 at 16:54
  • $\begingroup$ @user103296 Well, that works. So does this. puts on sensei outfit There are many paths to the top of the mountain, Grasshopper. $\endgroup$ – Rick Decker Nov 20 '17 at 17:54
  • $\begingroup$ @cort: a DFA is not the same as a Turing machine. The language it recognizes is certainly regular. $\endgroup$ – rici Nov 20 '17 at 18: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.