1
$\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

$\endgroup$

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.

  • 2
    $\begingroup$ Your solution doesn't accept $abab$. $\endgroup$ – Pseudonym Jan 15 '14 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 Jan 15 '14 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 Jan 15 '14 at 8:34
  • 5
    $\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 Jan 15 '14 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 Jan 15 '14 at 23:47
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?

$\endgroup$
4
$\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?

$\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)

$\endgroup$
  • 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 Jun 14 '15 at 16:25
  • $\begingroup$ user has asked only the DFA and by looking the DFA we can know how its working $\endgroup$ – Ravi Roy Aug 31 '15 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.

$\endgroup$

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.