# The set of words in {a,b,c}∗ that do not contain the substring bc.

I couldn't write nfa or dfa for the language above. Please, help me!

-
Please show what you have tried so far. –  Austin Mohr Nov 12 '12 at 20:08
Do you know a regular expression for that language? Because if you do, that makes the problem a bit easier. –  Brian M. Scott Nov 12 '12 at 20:09
I don't know regular expression but probably, all the options are possible. This is the question. –  linguist Nov 12 '12 at 20:21

One regular expression that generates that language is $c^*(b\cup ac^*)^*$; you might like to try designing a DFA from that. I’ll get you started, but you can stop reading this at any point and try to finish on your own. Let $s_0$ be the initial state. The empty word is in the language, so $s_0$ should be an acceptor state, and it should have a $c$ transition to itself; that part of the DFA handles the initial $c^*$ of the regular expression.

Then you’ll want states $s_a$ and $s_b$, with an $a$ transition from $s_0$ to $s_a$ and a $b$ transition from $s_0$ to $s_b$; $s_a$ is to start handling the $ac^*$ part of the regular expression, and $s_b$, the $b$ part. The $b$ part is simpler, so let’s start there. Since anything of the form $c^*b$ is in the language, $s_b$ has to be an acceptor state. If we make a $b$ transition from $s_b$ to itself, the DFA will accept anything of the form $c^*b^*$, which is fine. An $a$ input is also okay: we can include an $a$ transition from $s_b$ to $s_a$ to handle that, provided that we make $s_a$ an acceptor state. An input of $c$ when we’re at $s_b$ means that the input word is not in the language, so we want a fourth state, $s_g$, to be a ‘garbage’ state, a non-acceptor state with transitions only to itself where the machine goes as soon as it recognizes that an input is not in the language; there will be a $c$ transition from $s_b$ to $s_g$.

All that remains is for you to work out where the $a,b$, and $c$ transitions from $s_a$ should go.

-

Using Hagen von Eitzen's description here is a formal definition of your DFA $D=(Q,\Sigma,\delta,q_0,F)$:

States: $Q=\{q_0,q_b,q_\infty\}$

Alphabet: $\Sigma=\{a,b,c\}$

Transitions: $$\delta=\{\\((q_0,a),q_0),((q_0,b),q_b),((q_0,c),q_0),\\((q_b,a),q_0),((q_b,b),q_b),((q_b,c),q_\infty),\\((q_\infty,a),q_\infty),((q_\infty,b),q_\infty),((q_\infty,c),q_\infty)\\\}$$ where a tuple $((p,w),q)\in\delta$ denotes a transition $p\to q$ with input $w$.

Accepting states: $F=\{q_0,q_b\}$

The idea of this DFA is to keep track of the last input. Starting in $q_0$ if we read something which is not $b$ we don't care and jump "back" to $q_0$, however if we have the input $b$ we "remember" this by going to $q_b$. Then we check for $c$ and go then to $q_\infty$ to remain in such an error state, otherwise we don't care if it was $a$. Nevertheless if it was $b$ we need to "check" again whether we will find another possible occurence of $bc$.

Your DFA would look like

-
Let the states be Init, after b and error. States Init and after b are acceptiung states. From error, all arrows go to error. From Init and after b arrows with $a$ and $c$ go to Init, and the aorrow with $b$ goes to after b.