Can someone explain to me what this means in clear english and maybe give me a hint for how to make a NDFSM (non-deterministic finite state machine) that accepts this language? I understand that the 3 lined equal sign means mod. Does that mean that if a^n is divided by 3 you will get the same remainder as if ba^m were also divided by 3? Not entirely sure how to go about making a NDFSM for that if that's even correct. Any help would be appreciated. Here is the language:
On
$a^n$ here means the symbol $a$ repeated $n$ times. The language is of strings where the number of $a$s on the left and the number of $a$s on the right side of $b$ have the same remained divided by $3$.
To write the automata consider all three possible remainders of $3$. That is, the language is a combination of $a^{3n}ba^{3m}$, $a^{3n}aba^{3m}a$ and $a^{3n}aaba^{3m}aa$.
The words in this language are of the form $$ \underset{\text{n times a}}{aaa\ldots a}b\underset{\text{m times a}}{aaa\ldots a} $$
such that $n-m$ is a multiple of $3$, this exactly means that the reminder of $m$ and $n$ when divided by $3$ is the same.
In short, for $n$ times $a$ we write $a^{n}$ and similarly we write $a^{m}$ to represent a sequence of $m$ $a$'s.
For a NDFSM: Consider the following hint: You start of by reading $a's$ (until you have read the first $b$), you would like to remember what is the reminder of $n$ when divided by $3$ so after reading the $b$ you will know what the reminder of $m$ when divided by $3$ should be like.
You can star of with $3$ states that represents the reminder $(0,1$ or $2$). Then after reading the $b$, depending on the path you can know what is $n$(mod $3$), and in a similar way check that $m$(mod $3$) is the same.