Детерминиране на КНА

[Гост]

Детерминизация на КНА (крайно нетедерминиран автомат)
http://postimg.org/image/mqp8o73ht/
Искам да попитам ако някой ги разбира тези неща каква е логиката на отпадне на редовете,кои редове отпадат.Тези задрасканите ясно защо отпадат(празното множество отпада винаги ) но другите ( 4 и 6) защо отпадат?

[drago]

Ред 3 отпада, не защото там някъде вдясно е написано празното мн., а защото [tex]\{z_1\}[/tex]го няма никъде в дясните колони (под а-тата и b-тата). Просто до такова състояние никога не се достига и затова няма смисъл да се упоменава в правилата на съотв. ДКА. (за съжаление не си показал правилата на съотв. НКА, но предполагам, че началното му състояние е [tex]z_0[/tex]). По същата причина отпада и ред 4-ти.- просто не може да се достигне до състояние [tex]\{z_2\}[/tex] -няма го в колонките под а-тата и b-тата. Махайки 4-ти, махаме и 6-ти по същата причина. След това, ако желаеш, може и да нарисуваш еквивалентния ДКА.
Най-добре си прочети смисъла на метода, с който от НДА се конструира ДКА, не заучавай самия алгоритъм механично. Ако учебника не е написан идейно, а само алгоритмично, виж в нета, търси примерно nondeterministic finite automaton, или пък powerset construction и вникни в смисъла.
П.П. Имаше навремето един хубав учебник на български- Дискретна математика на Радослав Павлов (всъщност по него съм учил във ФМИ), друга подобна литература за препоръчване на български не съм срещал.