Search code examples
finite-automatastate-machine

Can {a,b,c}*a^n{a,b,c}*b^n{a,b,c}*c^n{a,b,c} be accepted by an FSA?

I'm looking at some exercices that reguards FSAs and my teacher is giving and odd solution for the language

enter image description here

I would have solved that language with a Not-Deterministic TM cause you have to remember n for a, b and c.

This is the given solution enter image description here Is this solution incorrect?

Solution

  • The example above does work and therefore is correct. It is clear that for n = 1 the FSA posted above does work. Now let's condiser the case n > 1, we have to have the same amount of a, b and c between every possible string composed of {a,b,c}. This string can be seen as the same string with n = 1 and the other n - 1 repetitions can be put in the {a,b,c}* group of strings, hence this FSA can accept that language correctly.