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
$\begingroup$
$\endgroup$
3
-
$\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$– fade2blackCommented Nov 20, 2017 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$– user103296Commented Nov 20, 2017 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$– fade2blackCommented Nov 20, 2017 at 17:11
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
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.
answered Nov 20, 2017 at 15:58
-
$\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$ Commented Nov 20, 2017 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$ Commented Nov 20, 2017 at 16:41
-
$\begingroup$ I was taught to start with a regular expression, then make a NFA, then convert that to a DFA. $\endgroup$ Commented Nov 20, 2017 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$ Commented Nov 20, 2017 at 17:54
-
$\begingroup$ @cort: a DFA is not the same as a Turing machine. The language it recognizes is certainly regular. $\endgroup$– riciCommented Nov 20, 2017 at 18:49
$\begingroup$
$\endgroup$
2
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).
answered Nov 20, 2017 at 15:26
-
$\begingroup$ In the language are CB, ABCA, BBACBA. Using ∩ wouldn't allow this would it? $\endgroup$ Commented Nov 20, 2017 at 15:53
-
$\begingroup$ @user103296 Yes, the intersection accepts these strings strings. $\endgroup$ Commented Nov 20, 2017 at 16:55