# Create a Deterministic Finite Automaton for a regular expression

I want to create a finite state machine that accepts the following language:

$$L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\}$$

So I began by writing a regular expression from this and this is what I came up with:

$$(a+b)(a+b)^*abb(a+b)^*$$

And for the finite state machine I tried to do this: But it doesn't work since I can go from qo->(a)q1->(b)->(b)q1 and have $$abb$$ at the begining. How should I approach this? How should I approach to create a finite state machine when for example I have the regular expression? How should I develop an intuition without using algorithms such as FollowPos?

I think your problem could be understood in two ways:

1. $$abb$$ is a subword of $$w$$ and the word $$w$$ doesn't start with $$abb$$
2. $$abb$$ is a subword of $$w[1:]$$, but the word $$w$$ can start with $$abb$$

I will assume the first one but correct me if I'm wrong.

One way to create an automaton for this language would be as follows:

1. From the start state $$q_0$$ go to $$q_a$$ on input $$a$$ and to $$q_{abb?}$$ on input $$b$$
2. From $$q_a$$ go to $$q_{ab}$$ on $$b$$ and to $$q_{bb?}$$ on $$a$$
3. From $$q_{ab}$$ go to $$q_{reject}$$ on $$b$$ and to $$q_{bb?}$$ on $$a$$
4. From $$q_{abb?}$$ loop on $$b$$ and go to $$q_{bb?}$$ on $$a$$
5. From $$q_{bb?}$$ go to $$q_{b?}$$ on $$b$$ and loop on $$a$$
6. From $$q_{b?}$$ go to $$q_{accept}$$ on $$b$$ and to $$q_{bb?}$$ on $$a$$
7. Loop on $$q_{accept}$$, which is the accepting state

The graphical representation would look as follows: So what we are doing, in essence, is first checking if the word $$w$$ starts with $$abb$$ and if it does reject it and if it does not, then look for the subword $$abb$$.

• Why did you call the state : $q_{abb?}$ that way? Because at that point you only have a $b$? Nov 18 '20 at 14:13
• The idea behind the states $q_{x?}$ is that we have still yet the word $x$ to see in order to find the subword $abb$. For example $q_{abb?}$ means we still have to see the whole $abb$, the state $q_{bb?}$ means we saw $a$ and we need to see $bb$ now to find $abb$ and so on Nov 18 '20 at 14:20