Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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."
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.
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$.
