Прочетох текстов файл със символи, състояния и преходи и го поставих в таблица. Изглежда така:
символи a, b
състояния q1, q2, q3, q4
начално състояние q4
крайно състояние q2, q3
преходно състояние:
q4, епсилон, q1
q1, a, q2
q3, a, q3
q3, b, q1
Четох алгоритъм за това как да конвертирам NFA в DFA, но не разбирам наистина алгоритъма. Как да създам методи за преход и какъв клас трябва да имам?
имам страхотна връзка тук: JFLAP
JFLAP е Java JAR, който има включена хубава визуализация. Можете да тествате и трансформирате NFA/DFA, да правите Pumping Lemma Stuff и да проверявате различни граматики и други подобни... Може да опитате!
Имате ли проблем с програмирането или проблем с Automata?
Тъй като програмирането изглежда много просто. Да, ще имате клас състояние с 4 възможни стойности q1-a4. Класът на състоянието има един конструктор, който го инициализира към q4. Има функция Accept(symbol), която модифицира обекта на състояние, и евентуално функция IsEndState(), която връща true за състояния q2 и q3.
Частта NFA/DFA влиза в действие при внедряването на метода Accept(). Сега може да бъдете помолени за програмно решение за преобразуване на NFA-базирана реализация на Accept() в DFA-базирана реализация на Accept().
Тези две връзки трябва да ви помогнат:
http://www.win.tue.nl/prose/pres/ploeger-19-10-06.pdf
http://www.cs.sun.ac.za/rw711/documentation/hopcroft2.pdf
Ако искате да го направите автоматично, без да се налага да изтегляте нещо като JFLAP, дайте онлайн NFA на DFA инструмент за преобразуване завъртане.
Видеоклипът „Конвертиране на NFA в DFA“ на ProfBrown в YouTube разглежда как да го направите в някои строгост, въпреки че IMO е непрактично и ненужно досадно да трябва да пишете таблиците на ръка. Когато свикнете да извършвате процеса, ще можете да го наблюдавате за малки графики. В случай на големи графики, така или иначе бихте използвали инструмент за автоматизиране.
