I have been asked to give a formal description of a finite state machine. I have tried for over five hours to minimize it, to understand what gets accepted, and what gets refused, to no avail. I really am in need of help. If solving the problem does not seem reasonable, I would really appreciate any tips to attack this problem. The machine looks as such:
Things I've tried: I tried minimizing it, but the minimized version no longer accepts the same language. I tried looking at what gets accepted. I looked at how one can reach state q1 (through loops and what not), and how one can reach state q4 (through the same idea). When I tried this, I couldn't find a reasonable answer. Example:
For q1: 4 ways to get to q1:
a run of a's,
loops of the manner (q1->q2->q3->q1),
loops of the manner (q1->q2->q4->q3->q1),
and loops of the manner (q1->q2->q4->q3->q2->q4->q1).
I would follow a similar thought process for arriving to q4. However, I can't seem to write a language that encompasses all of the possible combinations of these, along with the union of the two. I appreciate any help. Thank you very much.
EDIT: My attempt at minimizing the state machine :
The 0 equivalence looks like this: [Q2 Q3] [Q1 Q4]
1 equivalence looks the same
This means we only have two states. I'll denote [Q1 Q4] by A, and [Q2 Q3] by B. Initial and final state is A, and the other is B, which is not final.
A on a goes to A, A on b goes to B.
B on a goes to B, B on b goes to A.
In the initial machine, bbb is accepted, but not in the minimized version. Hence, I don't know where I went wrong.