Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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.

share|cite|improve this answer

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

enter image description here

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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