As said the answer is pretty simple "no", but that is not what i encountered. Here is the summary : i took a regular language , produced two ways of accepting same language (the ways in my understanding produce same language -please correct me if i am wrong ),then formed the minimal DFA for both of them,used equivalence method to show they are equal-by making table(i call it as like this but ,may be you say it something different you will know when you see the table). But contrary to this that for all language there exist a single minimal dfa.I found that both minimal dfa formed by my method can't be reduced to a single minimal dfa . which means for a language we could have 2 minimal dfa (here i found 2 , they could be more by this result)

I used two language , here in L1 i used "absolute function" in"|n(a)- n(b) |" ,

L1 ={ |n(a) - n(b)|=3m ,m is set of integers(positive or negative-but be aware the it hardly makes any difference if "m" is negative ,as we have used "absolute function" on the difference so "m" will always positive}. here "n(a)" is number of "a" in the string and similarly n(b). In simple words " L1 is the language generated by taking absolute difference of (n(a)-n(b)) and then checking that the length of string is divisible by 3 or not ".

Now comes the second language L2 = {(n(a) - n(b))mod 3 = 0 }

below are my methods used please correct me where i am wrong.here are my calculations

  • 1
    $\begingroup$ The minimal DFA is unique. You can find a proof in many textbooks. $\endgroup$ – Yuval Filmus Oct 25 '18 at 5:58
  • $\begingroup$ Your two DFAs have a different number of states. A DFA is minimal if it has the minimum number of states. So one of your DFAs isn't minimal. $\endgroup$ – Yuval Filmus Oct 25 '18 at 6:00
  • $\begingroup$ Yeah but iam unable to minimise the dfa1 to dfa2 so there must be something wrong here, I request you to please look in to this $\endgroup$ – Noob Oct 25 '18 at 6:03
  • $\begingroup$ You must be applying the minimization algorithm incorrectly. $\endgroup$ – Yuval Filmus Oct 25 '18 at 6:04
  • $\begingroup$ @YuvalFilmus thanks for you valuable suggestion , i found my mistake , so thanks , actually it was in the minimisation ,so iam taking this question down $\endgroup$ – Noob Oct 26 '18 at 1:56

After looking closely again to the minimization of the dfa1 you will found that dfa1 = dfa2 so both the language are equal.

during minimisation of dfa1 you will find that state 1=4 and 2=3 hence the final combination will be

$\pi$0 ={1,2,3,4} {0} (0 length-(by length i mean length of string) equivalent)

$\pi$1 = {1,4} {2,4} {0} (1 length equivalent )

$\pi$3 = {1,4} {2,4} {0} ( 2 length equivalence)

hence $\pi$2 =$\pi$3 means the dfa1 has been minimized. And when you make the tansition-table of minimized dfa1 its equal to dfa2.


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.