0

enter image description here

Hi!

Using table-filling method, how do I prove that states A and B are distinguishable? A,C and B,C initially marked pairs are obviously allright, but then when I look at A,B , there is no symbol s in the alphabet {1,2,3} that I can use to analyze a pair of "simultaneous" transitions sigma(A, s) and sigma(B, s), where sigma is a transition function.

Is this method unfit for the task? If that is the case, what would you recommend to use instead (I'm writing a program that takes DFA on ASCII alphabet and minimizes it)?

Boris-Barboris
  • 23
  • quoting Basics of Compiler Design by Torben Ægidius Mogensen

    "If two states s1 and s2 have transitions on the same symbol c to states t1 and t2 that we have already proven to be different, then s1 and s2 are different. This also applies if only one of s1 or s2 have a defined transition on c."

    Looks like this situation automatically means distinguished states.

     – Boris-Barboris Sep 07 '17 at 22:20

1 Answers1

0

Looks like table filling works only for complete automata. I have to either introduce a dead state and create fictional transitions into it from all the states that are incomplete (and self-transition from the dead state to dead state for each letter of the alphabet), or use specialized minimization algorithm, for example https://arxiv.org/pdf/0802.2826.pdf

Boris-Barboris
  • 23