Finding a language for a NFSA

Question

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

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!

Answer 1

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.

Answer 2

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".