DFA for exactly two of a and one or more of b
I'm totally new to DFA's and automaton in general -- this is the first week or two of class that I've actually seen this -- and I'm curious as to a pattern to match the following:
"Match the set of all strings on the alphabet {a, b} that have at least one b and exactly 2 a's"
I've tried to construct a DFA to represent this structure, but I have no idea how to form a structure to count for something and match for one.
Can someone help?
Okay, so. Here's what I got and I think it's the right answer.
Asked By : alvonellos
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/19736
Answered By : Pseudonym
If you're stuck on problems like this, it often helps to try to construct a regular expression first. Note that it's perfectly acceptable to make it the union of overlapping REs.
The RE $b^* a b^* a b^*$ accepts strings with exactly two $a$'s, but doesn't take into account that there must be a $b$. A $b$ could be in any of the $b^*$ parts, so this RE accepts the language:
$$(b b^*) a b^* a b^* \cup b^* a (b b^*) a b^* \cup b^* a b^* a (b b^*)$$
Did that help?
Post a Comment