[C++] Перевод НКА в ДКА
НКА - недетерминированный конечный автомат
ДКА - детерминированный конечный автомат
Пример:
Входной алвфит А(q0,q1,q2)
////////////0/////////1
->q0 | {q0,q1} | {q0}
q1 |////////////| {q2}
*q2 |////////////|
q0 – начальное состояние
q2 – заключительное состояние
Конструкция подмножеств:
/////////////0/////////1
{q0} | {q0,q1} | {q0}
{q1} | {пустое} | {q2}
{q2} | {пустое} | {пустое}
{q0,q1} | {q0,q1} | {q0,q2}
{q0,q2} | {q0,q1} | {q0}
{q1,q2} | {пустое} | {q2}
{q0,q1,q2} | {q0,q1} | {q0,q2}
{пустое} | {пустое} | {пустое}
/// - это означает пустое пространство
P.S. Заранее спасибо!