This question already has an answer here:

$\{ w∈(a,b)^\ast | w $ does not contain '$ab$' as a subword $\}$.

About questions like this, I always want to construct the regular expression for it, then convert the regular expression to a finite automata. Is there an easier way? Actually, I dont know the regular expression of it either.


marked as duplicate by Evil, David Richerby, Yuval Filmus formal-languages Apr 21 at 3:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Apr 17 at 19:12
  • $\begingroup$ This is a language where constructing the NFA directly is probably simpler. Since the "language predicate" is a negation, it may be prudent to start with a rejecting path, then fill in the accepting rest. $\endgroup$ – Raphael Apr 17 at 19:13
  • $\begingroup$ cs.stackexchange.com/q/45570/755, cs.stackexchange.com/q/1331/755 $\endgroup$ – D.W. Apr 17 at 20:16

It helps to think of finite automata in terms of their states. That is, think of what should each state represent for designing a finite automaton. In fact, it helps to "be the automaton". For this problem, you could start like, Initially, we are at the "start" state, say S1. Now we see an "a", what do we do? We have matched part of the ab substring, so we now need to check if we get a "b" next in line. So this state "waiting for a "b"" is a new state, say S2. Now at S1, we get a "b". This doesn't change anything, we still haven't got an "a" so we continue to remain in S1, waiting for an "a" to match and move to S2. At S2 if we get a "b", we have an "ab" now, so I move to a new "matched ab" state, say S3. At S2, if we get an "a", then we are still in the "matched a" state, and continue to wait for B. Try to think this way, and you shall probably find it easier to design automata, I found this intuition helpful.


The idea of a finite automaton is that each state stands for a combination of following kinds of properties.

  • properties of the whole string, which basically determine whether the string should be accepted or not.
  • what are the last several letters of a string, which basically determine the transitions between the states when another character is appended to the string.

For the language in the question, the relevant properties are
$\quad$- whether the string contains $ab$
$\quad$- the last character of the string
So there are about $2\times 2 = 4$ states.
$\quad$ $q_{\epsilon}$: the empty string.
$\quad$ $q_{\text{no}, a}$: strings that do not contains $ab$, ending with $a$.
$\quad$ $q_{\text{no}, b}$: strings that do not contains $ab$, ending with $b$.
$\quad$ $q_{\text{yes}, a}$: strings that contain $ab$, ending with $a$.
$\quad$ $q_{\text{yes}, b}$: strings that contain $ab$, ending with $b$.
The last two states can be merged as one state
$\quad$ $q_{yes}$: strings that contain $ab$.

Note that meaningful subscripts are used to indicate the properties associated to the states. Upon seeing ${q}_{\text{no},a}$, you know immediately the input that reaches this state does not contain $ab$ and it ends with $a$.

Exercise. Define a finite automata that accepts the language $\{w\in\{a,b\}^*\mid w\text{ contains } b\text{ but does not contain } bba\text{ as a subword}\}$.


Can you construct a FA for the language of all strings over $\{\texttt{a}, \texttt{b}\}$ that do contain $\texttt{ab}$? Given a finite automaton that accepts a language $L$, can you construct a new FA that accepts the complement of $L$? If so, you have your answer.


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