1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Sep 26 '15 at 17:03
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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^+} $$
$\endgroup$
1
$\begingroup$

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

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