Пусть задан недетерминированный конечный автомат (без пустых переходов)M = < {0, 1}, {q, p, s}, q, F={p}, Φ> с программойΦ: q 0 → p, q 0 → s, p 0 → q, p 0 → s, p 1 → p, s 1 → pКакие из следующих трех ДКА эквивалентны M?
M1 = < {0, 1}, {q, p, ps, qs}, q, F1={p, ps}, Φ1> с программойΦ1: q 0 → ps, q 1 → p, p 0 → qs, p 1 → p, ps 0 → qs, ps 1 → p, qs 0 → ps, qs 1 → p
M2 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ∅}, q, F2={p, ps, pq, qps}, Φ2> с программойΦ2: q 0 → ps, q 1 → p, p 0 → qs, p 1 → p, s 0→ ∅, s 1→ p, ps 0 → qs, ps 1 → p, qs 0 → ps, qs 1 → p, qp 0 → ps, qp 1 → p, qps 0 → qps, qps 1 → p, ∅ 0 →∅, ∅ 1 →∅.
M3 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ∅}, q, F3={ p, ps, pq, qps }, Φ3> с программойΦ3: q 0 → ps, q 1 → p, p 0 → qs, p 1 → p, s 1→ p, ps 0 → qs, ps 1 → p, qs 0 → qps, qs 1 →qps, qp 0 → ps, qp 1 → p, qps 0 → qps, qps 1 → p. ∅ 0 →∅, ∅ 1 → ∅