Create a Deterministic Finite Automaton for a regular expression

Question

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?

Answer 1

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

Answering the other part of your question:

1. There is an algorithm that transforms regular expressions to Nondeterministic Finite Automata
2. Developing intuition is just a matter of practice. You have to write as many automata for regular languages as possible and see what are the common tricks and methods, and what are some traps that await you when constructing automata.

Answer 2

Tentukan Bahasa regular dan gambarkan Finite Automata dari Regular ekspresi berikut :

 a. a (ba)*

 b. (ab)* a