I had this question in a school test:

Design a non-deterministic FSM that receives all words over {a,b,c} that:

  1. Start with cc.
  2. Contain at least 1 ab or aca.
  3. Ends with an odd number of (bc).

The FSM I built was wrong. However, when I asked the teacher for an FSM that works, she gave me this: Ignore the text (ignore the text).

From how I see it, this FSM doesn't work- because for example the word ccabcbc from the route


But she just says that the FSM works and that I don't understand how a non-deterministic FSM works.

So, am I wrong or is she? if I'm wrong, why is the route I gave not valid? And if I'm right, it would be great if someone could send an FSM that works, because I was struggling with this even at home.

Thanks in advance, and sorry for misuse of terms, I learn the subject in a different language.


Your professor is wrong. The task "accept an odd number of bc at the end" can only mean "accept only an odd number (and not an even number) of bc, since otherwise there would be no point in even stating the condition - every even number of repetitions also ends with an odd number of repetitions if you count from the right position.

So how do you write an automaton that accepts only an odd number of bc at the end? The trick is to ensure that the transitions immediately before the final loop don't accept bc. For instance, you could create seven different paths for all other two-symbol combinations and make sure that the final state is reachable only through them.

(This seems expensive, and it is. Negating conditions in regular languages is often surprisingly complicated. You may have learnt that regular languages are closed under negation, and that's true - it's always possible to create a machine that accepts the opposite of a language. But theory doesn't say that it will be cheap, and in fact it often isn't.)

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.