# DFA for at most two $b$'s and at least one $a$

I'm totally new to DFA's and automata 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 most two $b$'s and 1 or more $a$'s."

• What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. You may also want to check out our reference questions. – David Richerby Sep 26 '15 at 17:03

## 3 Answers

Close your eyes. Tell yourself: I am an automaton.

What is my task? Check whether the number of $a$'s is at most $1$ and the number of $b$'s is at least $2$. So I will count $a$'s and $b$'s. My memory holds two numbers, the respective counts. I start with two zero's. When I see $a$ I add one to the first number, when I read $b$ I add one to the second number.

Ah. When the number of $a$'s reaches $2$ I can stop counting them: my test be be always false. When the number of $b$'s equals $2$ I can stop counting them, I have seen enough of them.

Now open your eyes and write down your state diagram: all possible states (= memory contents) and actions upon reading a letter to another state. Mark the "good" states.

Done.

A standard idiom in situations like this is to use the states to "remember" the number of $a$s and $b$s seen so far, so we can list the states as $s_{p,q}$, with the interpretation that if you're in state $s_{p,q}$, then you have seen $p$ $a$s and $q$ $b$s.

Now the $p$ that are of interest to us are $p=0$ and $p\ge 1$. The $p\ge 1$ values are the ones we'll accept. Similarly, the $q$ that are of interest to us are $q=0, 1, 2$ and $q>2$ and we'll accept $q=0,1, 2$. Combining these, we'll have eight states corresponding to the pairs $$(0, 0)\quad(0,1)\quad(0, 2)\quad (0, 3^+)\quad(1^+, 0)\quad(1^+,1)\quad(1^+, 2)\quad (1^+, 3^+)$$ where the notation $n^+$ means the relevant variable is greater than or equal to $n$

Since you want to accept strings where the number of $a$s to be greater than or equal to 1 AND the number of $b$s is $0,1,2$ the final states of this FA will be $$s_{1^+,0}\quad s_{1^+,1}\quad s_{1^+,2}$$ Filling the transitions is easy. For example, in state $s_{0,2}$ seeing an $a$ the machine will change to $s_{1,2}$ and seeing a $b$ will change to $s_{0,3^+}$. Do this for all eight states and you'll have completed the FA.

1. This is known as the Cartesian product of two finite automata. I didn't come across a good online source for this, but it's in many theory texts.
2. This construction will work for other conditions as well. For instance if you had wanted a machine to accept strings with 1 or more $a$s OR 2 or less $b$s, you'd construct exactly the same FA but the final states would be $$s_{0,0}\quad s_{0,1}\quad s_{0,2}\quad s_{1^+,0}\quad s_{1^+,1}\quad s_{1^+,2} \quad s_{1^+,3^+}$$

Hint. Try first to find the set $S_0$ of strings that have no $b$'s and $1$ or more $a$'s, then the set $S_1$ of strings that have exactly one $b$ and $1$ or more $a$'s and finally the set $S_2$ of strings that have exactly two $b$'s and $1$ or more $a$'s.

You should be able to find a regular expression for $S_0$ and $S_1$ by yourself and this should help you to find one for $S_2$. The language you are looking for is the union of $S_0$, $S_1$ and $S_2$.