0
$\begingroup$

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: Finite state machine

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: enter image description here

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: enter image description here

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

$\endgroup$

migrated from stackoverflow.com Sep 27 '17 at 7:59

This question came from our site for professional and enthusiast programmers.

  • 1
    $\begingroup$ 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. $\endgroup$ – templatetypedef Sep 26 '17 at 23:15
  • 2
    $\begingroup$ 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? $\endgroup$ – templatetypedef Sep 26 '17 at 23:16
  • $\begingroup$ 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. $\endgroup$ – R.DM Sep 26 '17 at 23:18
1
$\begingroup$

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^*$.

There might be a simpler description.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.