How to construct the DFA for the following question?

Question

Given $L=\{ab^5 w b^4 \}$ where $w=\{a,b\}^*$.

I am not able to construct it, I tried it but getting problems with the transitions for input symbol a.

Answer 1

The language $L$ consists of all strings start start with an $a$, then five $b$'s, then any any number of $a$'s and $b$'s (including none) and four $b$'s at the end.

Thus, a DFA that recognises $L$ can be described as follows. The start state only has an $a$-transition to the next state, and the following five states only have $b$-transitions to the next state. This takes care of the $ab^5$ part. Now, we need to be able to accept any number of $a$'s and $b$'s before we read four $b$'s. So the next state will have an $a$-transition going to itself, and a $b$-transition to the next state. The next state will also have a $b$-transition going to the following state, but it will furthermore have an $a$-transition going back to the previous state, because the $b$ we just read may have been part of the $w$ and not the four last $b$'s. The same happens with the next two states, and the state after that will be the accept state. In the accept state, we still need to be able to go back to the state with the $a$-loop, but we also need a $b$-loop, because the string may end with any number of $b$'s.

All in all, this gives us a DFA like the following.

EDIT: As Sebastian Bechtel pointed out in another answer, the DFA in the drawing implicitly goes to a "fail" state which has $a$- and $b$-loops whenever a symbol is read for which there is no corresponding outgoing transition in the given state (as for example there is no $b$-transition in the first state).

Answer 2

Do it as suggested by mrp but you have to make his automaton deterministic. This is easy, just add a new "dead" state and add transitions from the first 6 states to it with for the symbol that was not yet used on those states. This new state has transitions into itself for both a and b.