Deterministic finite automata

Question

For this question about Deterministic finite automata:

Is this answer:

bbbb, bbba, bbab, bbaa, b, a correct?

Answer 1

I’m going to assume that the picture shows two distinct DFAs, and that the blue states are the acceptor states. The top DFA accepts precisely those strings that contain exactly two $b$s and end with a $b$; the corresponding regular expression is $a^*ba^*b$. The strings of that kind of length at most $4$ are

$$bb,abb,bab,aabb,abab,baab\;.$$

It’s a little harder to work out a general description of the strings accepted by the bottom DFA, but it’s easy enough to go through the possible strings of length at most $4$ to see which are accepted. Since the initial state is an acceptor state, $\lambda$, the empty string, is accepted. So are $a$, since it takes you to the second acceptor state, and $b$, since it leaves you in the initial state. If a string starts with $a$, a $b$ is going to take it to the trap state at the end, where it will never be accepted, but any number of $a$s will leave it in the second acceptor state, so $aa,aaa$, and $aaaa$ are all accepted. If it starts with $b$, an $a$ will take you to the second acceptor state, so $ba$ is accepted, as is $bb$, which leaves you in the initial state. A $b$ after $ba$ ensures that the string won’t be accepted, but $baa$ and $baaa$ are accepted, as are $bbb, bbba$, and $bbbb$. The complete list of words of length at most $4$ accepted by the bottom DFA is therefore

$$\lambda,a,b,aa,ba,bb,aaa,baa,bba,aaaa,baaa,bbaa,bbba,bbbb\;.$$

By this point you should be able to see that the bottom DFA accepts precisely those strings that start with any number of $b$s (including none at all) followed by any number of $a$s (including none at all); the corresponding regular expression is $b^*a^*$.

The only string of length at most $4$ that is accepted by both DFAs is therefore $bb$.