Детермінізація НДСкА: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
м r2.7.3) (робот додав: fa:ساختمان پاورست |
Іванко1 (обговорення | внесок) м суміш розкладок за допомогою AWB |
||
Рядок 31:
Метод: Алгоритм тримає набір поточних станів <math>S</math>, які наразі були досягнуті читанням рядка. Якщо <math>c</math> — наступний вхідний символ, читаємо функцією ''nextchar()'', тоді спочатку обчислюємо ''move(S, c)'' і потім замикаємо цю множину за допомогою ''ε-closure()''.
1: S =
2: c = nextchar();
3: while ( c != eof ) {
4: S =
5: c = nextchar();
6: }
7: if ( S
8: else return "no";
Рядок 46:
# Двомірний масив ''move[s, a]'', що містить таблицю переходів НСА. Записи в цій таблиці, які є наборами станів, представлені зв'язними списками.
Для втілення рядка (1), ми маємо встановити кожний запис масиву alreadyOn у FALSE, тоді для кожного стану ''s'' в ''c-closure(so)'', заштовхнути ''s'' у стек ''oldStates'' і встановити alreadyOn[s] в TRUE.
9: addState(s) {
10: push s onto newStates;
11: alreadyOn[s] = TRUE;
12: for ( t on move[s,
13: if ( !alreadyOn(t) )
14: addState(t) ;
| |||