I'm having a bit of trouble determining what language the following non-deterministic finite state automaton accepts.

enter image description here

Assuming the alphabet of this machine is ${a, b}$, I deduced that this automaton would accept words of the following characteristic: a word $w$ would be accepted if $w$ had zero or more $a$'s or $b$'s followed by a single $a$ followed by zero or more $a$'s or $b$'s followed by a single $a$ followed by zero or more $a$'s and $b$'s.

Is there a more clear and concise explanation of what sorts of words are accepted by this automaton or would my explanation be suffice? Any suggestions would be appreciated!


2 Answers 2


You have correctly identified your alphabet, but your verbal description is, indeed,complex. Your NSA would accept any string with at least 2 as.

There are many ways to describe NSAs. A regular expression or a regular grammar could be appropriate here. If this is for class, I would ask your professor what format he or she prefers.


Let's trace it together:

  • On q1 state, you are looping on a or b, or you can proceed. That means (a|b|E)*, which can be simplified to a*b*.
  • Then you move to q2 on an a, which means a*b*a.
  • Then on q2, it is the same as q1. Creating the expression a*b*aa*b*.
  • Then transition on a: a*b*aa*b*a
  • And looping on a or b: a*b*aa*b*aa*b*.

If your alphabet only contains a and b, then a*b* covers all combinations. The above expression can be comprehended as "<anything>a<anything>a<anything>", which can be verbally summarized as "strings that contain at least 2 occurrences of a".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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