0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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: enter image description here

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.
$\endgroup$
4
  • $\begingroup$ Hello, thanks for the answer. Yes, I think indeed it is the first one. Can you create a drawing, please? $\endgroup$
    – C. Cristi
    Nov 18 '20 at 12:41
  • $\begingroup$ Sure thing, I will edit my answer in a second :) $\endgroup$ Nov 18 '20 at 12:42
  • $\begingroup$ Why did you call the state : $q_{abb?}$ that way? Because at that point you only have a $b$? $\endgroup$
    – C. Cristi
    Nov 18 '20 at 14:13
  • $\begingroup$ 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 $\endgroup$ Nov 18 '20 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.