DFA for exactly two of a and one or more of b

Question Detail: 

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. dfa

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?

No comments

Powered by Blogger.