# Figuring out the language accepted by a DFA?

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 :

I look at the state diagram of the state machine, which looks something like the following:

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.

resulting in the following state machine:

In the initial machine, bbb is accepted, but not in the minimized version. Hence, I don't know where I went wrong.

• Are you familiar with the state elimination algorithm for converting a DFA to a regular expression? That's often a reasonable tool to use when you want to build a better intuition for a DFA. – templatetypedef Sep 26 '17 at 23:15
• Also, if your minimized DFA has a different language than the original DFA, it means that you made an error in one of your minimization steps; the minimized DFA always has the same language as the input DFA. Could you show your work there? – templatetypedef Sep 26 '17 at 23:16
• Thank you for your reply. I'll edit in order to add my steps for minimizing. I greatly appreciate your help. As for state elimination algorithm for converting a DFA to a regular expression, I have not yet heard of it, but I'll make sure to look into it. Again, thank you. – R.DM Sep 26 '17 at 23:18

The DFA is already minimal. In the table below, I give words which separate all pairs of states: $$\begin{array}{c|c|c|c|c} & q_1 & q_2 & q_3 & q_4 \\\hline q_1 & & \epsilon & \epsilon & b \\\hline q_2 & \epsilon & & ba & \epsilon \\\hline q_3 & \epsilon & ba & & \epsilon \\\hline q_4 & b & \epsilon & \epsilon & \\ \end{array}$$ As for the language accepted by this DFA, the best I got is \begin{align*} &(a^? (a^{even} b)^+ a^{odd} b)^* a^* + \\ &(a^? (a^{even} b)^+ a^{odd} b)^* a^?(a^{even} b)^+a^{even} b, \end{align*} where $a^? = a + \epsilon$, $a^{even} = (aa)^*$, $a^{odd}=a(aa)^*$, and $r^+ = rr^*$.