ДКА и НДКА

[collinsss123]

Здравейте група, имам огромен проблем. Имам изпит по "Автомати и изчислимост", темите, които са включени в изпита са ДКА, НДКА, Регулярни изрази. Та проблема идва от там, че не съм посещавала лекциите и лекциите, които са ми дадени, не са до толкова подробни и най-елементарните неща изобщо не мога да ги разбера.
Това са условията на задачите + решенията, но проблема е че колкото и да изчетох всички теории и всичко необходимо, просто няма директен отговор: това става така, после следва това и т.н. И просто не схващам всяко едно действие защо и кога трябва да се случи. Много ще се радвам, ако може някой просто да ми обясни накратко задачите.
Благодаря!

[ptj]

Виж си теоремата за минаване от НДКА към ДКА. Там е обяснен целия алгоритъм.

Не знам кой ви води упражненията и лекциите но последния автомат определено не ми харесва. Тези минавания от едно състояние в друго с празна дума [tex](\epsilon)[/tex] са ми меко казано странни...

По принцип ако езика рзпознава празната дума, само тогава трябва да има стрелка от начално към крайно състояние през епсилон.

Колкото до задачите -няма нишо сложно. Четеш последевателно символите на думите от езика, а когато ти трябва цикъл връщаш стрелка към съответнто състояние. Т.е. едно завъртане на цикъла да съответсва на последователност от стрелки през състояния посредством последователността от букви в него.

Опитай първо с елементарни конструкции, после с обединение на автомати.
Накрая може да използваш теоремата за построяване на допълнение на даден език до пълното множество (стига да стигнеш до там).

П.П. Потърси в сайта на ФМИ-Пловдив за лекции по дискретна математика. Автор- за предпочитане професор дмн Степан Костадинов или доцент Христо Кискинов.

Още нещо - не се опитвай да правиш директно ДКА. Първо си прави НДКА, а само когато съответната задача го изисква ползвай теоремата за минаваме от НДКА към ДКА.

Например за първата задача езика ти е : [tex]\{1\{0,1\}^*00\}\cup\{0\}[/tex] (понеже 0 се дели на 4). Предполагам за него можеш да построиш НДКА. После чрез вече спомената теорема да го докараш до ДКА.

[aifC]

Не може да ти се обеснят задачите, като не ти ясна теорията, ако беше изчел/я всичко както твърдиш поне алгоритмите щеше да запомниш, които смея да кажа не са толкова трудни, в по напреднал етап при употрба на компилаторите и интерпретаторите става по интересно.