Понимание алгоритма минимизации DFA

Я пытаюсь понять этот алгоритм алгоритм минимизации DFA по адресу http://www.cs.umd.edu/class/fall2009/cmsc330/lectures/discussion2.pdf, где сказано:

while until there is no change in the table contents:
    For each pair of states (p,q) and each character a in the alphabet:
        if Distinct(p,q) is empty and Distinct(δ(p,a), δ(q,a)) is not empty:
            set distinct(p,q) to be x

Бит, который я не понимаю, это «Отличное (δ (p, a), δ (q, a))». Я думаю, что понимаю функцию перехода, где δ (p, a) = любое состояние достигается из p с входом a . но со следующим DFA:

http://i.stack.imgur.com/arZ8O.png

в результате получилась эта таблица:

imgur.com/Vg38ZDN.png

не должен ли (c,b) также быть помечен как x, поскольку different(δ(b,0), δ(c,0)) не пуст (d) ?


state-machine dfa deterministic finite-automata
person user2469083    schedule 09.06.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Distinct(δ(p,a), δ(q,a)) будет непустым, только если δ(p,a) и δ(q,a) различны. В вашем примере δ(b,0) и δ(c,0) равны d. Distinct(d, d) пуст, так как d не имеет смысла быть отличным от самого себя. Поскольку Distinct(d, d) пуст, мы не помечаем Distinct(c, b).

В общем, Distinct(p, p), где p — это состояние, всегда будет пустым. А еще лучше, мы не рассматриваем это, потому что это не имеет смысла.

person Duncan    schedule 10.06.2013