 |
Главная |
СВЕДЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА К ДЕТЕРМИНИРОВАННОМУ
 2019-12-29 |
 232 |
 Обсуждений (0) |
из
5.00
|
Процедура построения детерминированного автомата Ад, эквивалентного недетерминированному автомату Ан, задается следующими шагами:
1. Пометить первую строку таблицы переходов для Ад множеством начальных состояний автомата Ан. Применить к этому множеству шаг 2.
2. По данному множеству состояний В, помечающему строку таблицы переходов автомата Ад, для которой переходы еще не вычислены, вычислить те состояния автомата Ан, которые могут быть достигнуты из В с помощью каждого входного символа х, и поместить полученные множества состояний в соответствующие ячейки таблицы для автомата Ад. Символически это выражается так: если d – функция недетерминированных переходов, то функция детерминированных перехода d' задается формулой d'(B, x) = {S | S Î d (T, x), " Т Î В}
3. Для каждого нового множества, порожденного переходами на шаге 2, посмотреть, имеется ли уже в Ад строка, помеченная этим множеством. Если нет, то создать новую строку и пометить ее этим множеством. Если множество уже использовалось как метка, никаких действий не требуется.
4. Если в таблице автомата Ад есть строка, для которой еще не вычислены переходы, вернуться назад и применить к этой строке шаг 2. Если все переходы вычислены, перейти к шагу 5.
5. Пометить строку как допускающее состояние автомата Ад тогда и только тогда, когда она содержит допускающее состояние недетерминированного автомата. В противном случае пометить как отвергающее состояние.
Описанная процедура гарантирует, что детерминированный автомат не содержит недостижимых состояний.
В результате применения этого алгоритма от недетерминированного автомата (табл. 4, рис. 1) можно перейти к эквивалентному детерминированному автомату, таблица переходов которого приведена в таблице 5.
Таблица 5
Таблица переходов детерминированного автомата.
| x0 | x2 | x3 | x4 | x5 | x6 | x7 | ||
| {S} | {Er} | {Er} | {Er} | {Er} | {S1,S3} | {F} | {C} | 0 |
| {S1,S3} | {Er} | {Er} | {Er} | {Er} | {Er} | {S2,S4} | {Er} | 0 |
| {S2,S4} | {A} | {Er} | {Er} | {B} | {Er} | {Er} | {Er} | 0 |
| {A} | {Er} | {D} | {Er} | {Er} | {A1} | {Er} | {Er} | 0 |
| {A1} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 1 |
| {B} | {Er} | {E} | {Er} | {Er} | {B1} | {Er} | {Er} | 0 |
| {B1} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 1 |
| {C} | {Er} | {E} | {Er} | {Er} | {C1} | {Er} | {Er} | 0 |
| {C1} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 1 |
| {D} | {Er} | {S} | {D1} | {Er} | {Er} | {Er} | {Er} | 0 |
| {D1} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 1 |
| {E} | {Er} | {S} | {E1} | {Er} | {Er} | {Er} | {Er} | 0 |
| {E1} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 1 |
| {F} | {Er} | {F9} | {Er} | {Er} | {F5} | {Er} | {F1} | 0 |
| {F1} | {Er} | {Er} | {Er} | {Er} | {F2} | {Er} | {Er} | 0 |
| {F2} | {Er} | {Er} | {Er} | {F3} | {Er} | {Er} | {Er} | 0 |
| {F3} | {F4} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 0 |
| {F4} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 1 |
| {F5} | {Er} | {Er} | {Er} | {Er} | {F6} | {Er} | {Er} | 0 |
| {F6} | {Er} | {Er} | {Er} | {F7} | {Er} | {Er} | {Er} | 0 |
| {F7} | {F8} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 0 |
| {F8} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 1 |
| {F9} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {F10} | 0 |
| {F10} | {F11} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 0 |
| {F11} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 1 |
| {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | {Er} | 0 |
Перейдем к более простым обозначениям состояний автомата:
{S}®Y; {S1,S3}®Y1; {S2,S4}®Y2;
{A}®Y3; {A1}®Y4; {B}®Y5; {B1}®Y6;
{C}®Y7; {C1}®Y8; {D}®Y9; {D1}®Y10;
{E}®Y11; {E1}®Y12; {F}®Y13; {F1}®Y14;
{F2}®Y15; {F3}®Y16; {F4}®Y17; {F5}®Y18;
{F6}®Y19; {F7}®Y20; {F8}®Y21; {F9}®Y22;
{F10}®Y23; {F11}®Y24; {Er}®Er.
В новых обозначениях таблица переходов автомата приведена в табл. 6.
Таблица 6
Таблица переходов детерминированного автомата
(новые обозначения состояний)
| x0 | x2 | x3 | x4 | x5 | x6 | x7 | ||
| Y | Er | Er | Er | Er | Y1 | Y13 | Y7 | 0 |
| Y1 | Er | Er | Er | Er | Er | Y2 | Er | 0 |
| Y2 | Y3 | Er | Er | Y5 | Er | Er | Er | 0 |
| Y3 | Er | Y9 | Er | Er | Y4 | Er | Er | 0 |
| Y4 | Er | Er | Er | Er | Er | Er | Er | 1 |
| Y5 | Er | Y13 | Er | Er | Y6 | Er | Er | 0 |
| Y6 | Er | Er | Er | Er | Er | Er | Er | 1 |
| Y7 | Er | Y11 | Er | Er | Y8 | Er | Er | 0 |
| Y8 | Er | Er | Er | Er | Er | Er | Er | 1 |
| Y9 | Er | Y | Y10 | Er | Er | Er | Er | 0 |
| Y10 | Er | Er | Er | Er | Er | Er | Er | 1 |
| Y11 | Er | Y | Y12 | Er | Er | Er | Er | 0 |
| Y12 | Er | Er | Er | Er | Er | Er | Er | 1 |
| Y13 | Er | Y22 | Er | Er | Y18 | Er | Y14 | 0 |
| Y14 | Er | Er | Er | Er | Y15 | Er | Er | 0 |
| Y15 | Er | Er | Er | Y16 | Er | Er | Er | 0 |
| Y16 | Y17 | Er | Er | Er | Er | Er | Er | 0 |
| Y17 | Er | Er | Er | Er | Er | Er | Er | 1 |
| Y18 | Er | Er | Er | Er | Y19 | Er | Er | 0 |
| Y19 | Er | Er | Er | Y20 | Er | Er | Er | 0 |
| Y20 | Y21 | Er | Er | Er | Er | Er | Er | 0 |
| Y21 | Er | Er | Er | Er | Er | Er | Er | 1 |
| Y22 | Er | Er | Er | Er | Er | Er | Y23 | 0 |
| Y23 | Y24 | Er | Er | Er | Er | Er | Er | 0 |
| Y24 | Er | Er | Er | Er | Er | Er | Er | 1 |
| Er | Er | Er | Er | Er | Er | Er | Er | 0 |
Граф переходов автомата, построенный по таблице 6, показан на рис. 2.
Рис. 2 Граф переходов детерминированного автомата эквивалентного исходному
Примечание. Чтобы не загромождать рисунок, не изображено состояние Er а также дуги, ведущие в него из других состояний.
Построенный автомат не является минимальным, поэтому необходимо выполнить этап минимизации автомата, на котором строится минимальный (иначе – приведенный) автомат.
| 2019-12-29 |
232 |
Обсуждений (0) |
из
5.00
|
Обсуждение в статье: СВЕДЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА К ДЕТЕРМИНИРОВАННОМУ |
|
Обсуждений еще не было, будьте первым... ↓↓↓ |
Почему 1285321 студент выбрали МегаОбучалку...
Система поиска информации
Мобильная версия сайта
Удобная навигация
Нет шокирующей рекламы