Преобразование регулярных выражений в НКА
Заносим в множество Dstates состояние Т = — closure (s0) и оставляем это состояние не помеченным. Рассмотрим, как строится множество Dstates. Состояния из Dstates можно помечать. На этом все циклы завешаются. Этот алгоритм позволяет построить ДКА. Рассмотрим теперь сам метод: s — состояние, T — множество состояний. В цикле while существует Т, Т Dstates и Т — непомечено. Для выражения s* автомат M… Читать ещё >
Преобразование регулярных выражений в НКА (реферат, курсовая, диплом, контрольная)
Описывать лексику языка удобнее в форме регулярных выражений, а распознавать язык с помощью КА. Поэтому важно уметь преобразовывать определения языка в форме регулярных выражений в определение в форме КА. Такое преобразование предложил Kennet Thompson. Покажем его в форме диаграмм. Т — функция определения преобразования.
Регулярные выражения служат для описания регулярных множеств. Для распознавания регулярных множеств служат конечные автоматы.
1. Для выражения s|t автомат M (s|t):
2. Для выражения st автомат M (st):
3. Для выражения s* автомат M (s*) строится:
Преобразование НКА в ДКА
Входные данные: НКА — N. Нужно получить ДКА — D с множеством состояний Dstates и множеством переходов Dtrans. Этот ДКА должен быть таким, чтобы его язык был бы таким же, как и у НКА.
Рассмотрим теперь сам метод: s — состояние, T — множество состояний.
Для работы понадобятся функции:
- 1) — closure (s) — замыкание, которое вычисляет множество состояний НКА N, достижимых из состояния s черезпереходы.
- 2) — closure (T), которая выдает множество состояний автомата N, достижимых из состояния, принадлежащего Т, черезпереходы.
- 3) move (T, a) — переход. Она строит множество состояний автомата N, в которые есть переход по символу «а» из некоторого состояния, принадлежащего Т.
Рассмотрим, как строится множество Dstates. Состояния из Dstates можно помечать.
АЛГОРИТМ:
- 1) заносим в множество Dstates состояние Т = - closure (s0) и оставляем это состояние не помеченным.
- 2) в цикле while существует Т, Т Dstates и Т — непомечено
do begin.
- 1. помечаем состояние Т
- 2. в цикле для каждого входного символа «а», принадлежащего — алфавиту автомата, выполним следующее: вычислим множество U = - closure (move (T, a))
- 3. проверим, если U не принадлежит Dstates, тогда заносим U в Dstates непомеченным, т. е. (должны найти варианты переходов (оно должно быть обработано)). В множество Dstates заносим переход (Т, а, U).
На этом все циклы завешаются. Этот алгоритм позволяет построить ДКА.
При работе НКА нужно каждый раз вычислять множество состояний, в которые можно попасть по — переходам. Если примем такие переходы за состояние нового автомата, тогда получим ДКА.