2
$\begingroup$

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

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ Your solution doesn't accept $abab$. $\endgroup$
    – Pseudonym ♦
    Commented Jan 15, 2014 at 4:01
  • $\begingroup$ It can take a while to get used to them; it's also unreasonable to expect you to understand everything in a lecture or two. $\endgroup$
    – Dennis Meng
    Commented Jan 15, 2014 at 7:12
  • $\begingroup$ It would not have hurt to browse through our myriad of similar questions (finite-automata); you might have found e.g. this. $\endgroup$
    – Raphael
    Commented Jan 15, 2014 at 8:34
  • 6
    $\begingroup$ Assign meanings for the states. At any one time, one of the following is true: "I have seen no $a$s", "I have seen exactly one $a$", "I have seen two or more $a$s". Likewise, one of the following: "I have seen no $b$s", "I have seen one or more $b$s". Each pair of facts (one about $a$ and one about $b$) is a state; now add the transitions and so on. $\endgroup$
    – David Richerby
    Commented Jan 15, 2014 at 9:52
  • 1
    $\begingroup$ Sorry, my first comment wasn't quite right, as I misread the question. You need to distinguish between "exactly two $a$s" and "three or more $a$s" but you get the idea. In fact, your attempted answer does basically this. It contains a couple of bugs but it's close to right: there's no transition for $a$ from $q_3$ or for $b$ from $q_8$. States $q_5$, $q_6$ and $q_8$ are (or should be!) identical so you could replace them by a single state -- they're all accepting, you stay if you read $b$, you move to $q_9$ if you read $a$. Then you'd have exactly the automaton I was trying to suggest. :-) $\endgroup$
    – David Richerby
    Commented Jan 15, 2014 at 23:47

4 Answers 4

Reset to default
2
$\begingroup$

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?

Improve this answer
$\endgroup$
5
$\begingroup$

Since it's for class, I won't actually build the DFA for you, but I will give you a way to look at it that'll help.

  1. As far as $b$s go, you really only care about whether or not you've seen a $b$ so far in the string.
  2. As for $a$s, you care about whether you've seen 0, 1, 2, or more.

Each combination of scenarios for both letters (like "seen none of either" or "seen one of each" or "seen one $a$ and no $b$s") changes in its own way depending on whether you read another $a$ or $b$. How might you express that in a DFA?

Improve this answer
$\endgroup$
0
$\begingroup$

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

this Dfa will accept exactly two a's and one or more b. State q3 is having transistion on 'a' to q5(arrow is missing)

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Welcome to Computer Science! For this sort of question, there's probably more benefit in explaining how the automaton works than in giving the actual state diagram. That would help the asker be able to answer similar questions on their own in future. $\endgroup$
    – David Richerby
    Commented Jun 14, 2015 at 16:25
  • $\begingroup$ user has asked only the DFA and by looking the DFA we can know how its working $\endgroup$
    – Ravi Roy
    Commented Aug 31, 2015 at 2:33
0
$\begingroup$

This is a good example of the utility of the product construction. If you can construct an automaton for all strings containing at least one $b$, and another automaton for all strings containing exactly two $a$s, then you can take their product to obtain an automaton for the conjunct condition.

Improve this answer
$\endgroup$

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