Ндка в Дка, алгоритъм

[simeon88]

Не мога да разбера алгоритъма на решение на тази задача

зад 1. Конструирайте ДКА, еквивалентен на НДКА N = (Q , Σ ,δ, q0, F ), където
a) Q = {q0, q1, q2}, Σ = {a, b}, F = {q1} и

δ(q0,a)=q2
δ(q0,b)=q1,q2

δ(q1,a)=q2
δ(q1,b)=∅

δ(q2,a)=q0,q1
δ(q2,b)=q2

имайки ∅ имам налично:
1. Q′ = 2^Q , т.е. Q′ се състои от 2^|Q| на брой състояния;
2. δ′ (R, a) = S r∈R E(δ(r, a)) за всяко R ∈ Q′ и a ∈ Σ;
3. q′ 0 = E({q0});
4. F′ = {R ∈ Q′ | R ∩ F =6 ∅}, където E(R) еε-затварянето на R за всяко R ∈ Q′ , т.е.
E(R) = {q ∈ N | q може да бъде достигнато от състояние в R посредством нула или повече ε-прехода}

но честно казано освен 1. 2^{q0,q1,q2}={∅,{q0},{q1},{q2},{q0,q1},{q0,q2},{q2,q3},{q0,q1,q2}} не разбирам останалата част, ако може някой да ми помогне не да реша задачата, а да разбера алгоритъма на решение, ще съм благодарен.

[simeon88]

Погледнах един пример, значи в момента имаме

δ'({q0},a)={q2}
δ'({q0},b)={q1,q2}

δ'({q1},a)={q2}
δ'({q1},b)=∅

δ'({q2},a)={q0,q1}
δ'({q2},b)={q2}

Прилагайки за всички останали Q' (изброени горе "1."), просто правим ∪
Пример: δ'({q0,q1},a) = δ'({q0},a) ∪ δ'({q1},a) = {q2}
Получавайки:

δ'({q0,q1},a)={q2}
δ'({q0,q1},b)={q1,q2}

δ'({q0,q2},a)={q0,q1,q2}
δ'({q0,q2},b)={q0,q2}

δ'({q1,q2},a)={q0,q1,q2}
δ'({q1,q2},b)={q2}

δ'({q1,q2,q3},a)={q0,q1,q2}
δ'({q1,q2,q3},b)={q1,q2}

А финалните състояния са всички включващи Z (q1), тоест Z'={{q1},{q0,q1},{q1,q2},{q0,q1,q2}}
Бих бил благодарен ако някой може да ми потвърди, макар че отговора ми е верен според дадените ми отговори.

[simeon88]

зад 2. (Тук нямам отговори) Конструирате ДКА, еквивалентен на недетерминирания автомат A = (Q, Σ, δ, q0, F ),
където Q = {q0, q1, q2}, Σ = {a, b}, F = {q2} и

δ(q0,a)={q0}
δ(q0,b)={q1,q2}

δ(q1,a)={q1,q2}
δ(q1,b)={q1}

δ(q2,a)={q1}
δ(q2,b)={q0,q2}

A'=(Q', Σ, δ', q0, F' )
Q'=2^Q=2^{q0,q1,q2}={∅,{q0},{q1},{q2},{q0,q1},{q0,q2},{q1,q2},{q0,q1,q2}}
F'={{q2},{q0,q2},{q1,q2},{q0,q1,q2}}

δ'({q0},a)={q0}
δ'({q0},b)={q1,q2}

δ'({q1},a)={q1,q2}
δ'({q1},b)={q1}

δ'({q2},a)={q1}
δ'({q2},b)={q0,q2}

δ'({q0,q1},a)={q0,q1,q2}
δ'({q0,q1},b)={q1,q2}

δ'({q0,q2},a)={q0,q1}
δ'({q0,q2},b)={q0,q1,q2}

δ'({q1,q2},a)={q1,q2}
δ'({q1,q2},b)={q0,q1,q2}

δ'({q0,q1,q2},a)={q0,q1,q2}
δ'({q0,q1,q2},b)={q0,q1,q2}

След премахването на състояния които не могат да се достигнат получавам схемата

δ'({q0},a)={q0}
δ'({q0},b)={q1,q2}

δ'({q1,q2},a)={q1,q2}
δ'({q1,q2},b)={q0,q1,q2}

δ'({q0,q1,q2},a)={q0,q1,q2}
δ'({q0,q1,q2},b)={q0,q1,q2}

L={w | w има поне едно b}

Мнения по задачата, правилно ли решавам (правилна ли ми е решението).

[niai]

Правилно решаваш. Можеш обаче доста да си съкратиш работата, като не започваш с търсене на всички възможни състояния и после премахване на недостижимите, а директно получаваш само достижимите. Примерно на втората задача: тръгваш от началното състояние:
делтаприм(q0, a) = {q0}
делтаприм(q0, b) = {q1, q2}
Сега разглеждаш двете състояния, които се получават: {q0} и {q1, q2}, първото е разгледано, значи остава второто.
Когато спреш да получаваш неразгледани състояния, си готов. Улесняваш си работата доста. Ако някой хитрец ти даде автомат с пет състояния, който се свежда до такъв пак с пет, по твоя метод има бая да се потрудиш, докато го установиш.

ПП. На първата задача виждам две грешки в отговорите: делтаприм({q0,q2},b) = {q1, q2}, а не {q0, q2}, но {q0, q2} е недостижимо състояние, затова не ти излиза като грешка в окончателния отговор. А {q1, q2, q3} предполагам е просто от невнимание

ППП. На втората няма грешки в отговора, решението не съм ти го гледала цялото... мързи ме Но принципът ти е ясен.

[simeon88]

Благодаря