# Can there exist two minimal dfa for same regular language?

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.

• The minimal DFA is unique. You can find a proof in many textbooks. – Yuval Filmus Oct 25 '18 at 5:58
• 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. – Yuval Filmus Oct 25 '18 at 6:00
• 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 – Noob Oct 25 '18 at 6:03
• You must be applying the minimization algorithm incorrectly. – Yuval Filmus Oct 25 '18 at 6:04
• @YuvalFilmus thanks for you valuable suggestion , i found my mistake , so thanks , actually it was in the minimisation ,so iam taking this question down – Noob Oct 26 '18 at 1:56

$$\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.