Определение AFI для AFD

Сложность
Легкий 25%

AFI в AFD

Теорема Рабина-Скотта утверждает, что любой язык, распознаваемый автомат индетерминированное конечное может быть распознано детерминированный конечный автомат (решимость AFI в AFD). Следовательно, можно представить индетерминированный автомат детерминированным автоматом, этот процесс называется детерминацией.

Рассмотрим, например,недетерминированный конечный автомат (К, Т, М, И, Ж) следующие:
К = {S1, S2, S3, S4}
Т = {а, б, с}
M = {(S1,a,S1),(S1,a,S3),(S2,b,S2),(S2,b,S3),(S3,c,S3),(S3,c,S4) }
я = {S1, S2}
Ф = {С4}
соответствующий график следующий :

AFI в AFD

Затем мы строим состояния детерминированного конечного автомата (AFD) и их функцию перехода. Изначально он имеет единственное состояние, которое состоит из множества начальных состояний индетерминированного конечного автомата (AFI): в нашем примере начальным состоянием AFD является {S1, S2}.

Каждый раз, когда в AFD добавляется новое состояние, его функция перехода определяется путем объединения соответствующих строк в таблице переходов
АФИ: в нашем примере для состояния {S1, S2} мы делаем объединение линий, соответствующих S1 и S2, и определяем функцию перехода

AFI в AFD

Другими словами, когда мы находимся в состоянии «S1 или S2» и читаем a, мы переходим в состояние «S1 или S3» (M({S1, S2}, a) = {S1, S3}), когда мы находимся в состоянии «S1 или S2» и читаем a b, мы переходим в состояние «S2 или S3» (M({S1, S2}, b) = {S2, S3}), а когда мы находимся в состоянии «S1 или S2″ и читаем c, переходим в «пустое» состояние, соответствующее ошибочному состоянию (M({S1, S2}, c) = ∅.

Затем в AFD добавляются состояния {S1, S3} и {S2, S3}, и их переходная функция определяется по тому же принципу. Шаг за шагом мы строим следующую таблицу переходов для AFD:

AFI в AFD

Множество состояний AFD есть K' = {{S1, S2}, {S1, S3}, {S2, S3}, {S3, S4}}. Состояния AFD, содержащие конечное состояние AFI, являются конечными состояниями. Здесь AFI имеет единственное конечное состояние S4, а набор конечных состояний AFD равен F' = {{S3, S4}}. Этот AFD соответствует следующему графику:

AFI в AFD

Другой пример

Вот еще один пример определения AFI для AFD.

AFI в AFD

Практически мы шаг за шагом строим только доступные из I состояния: начинаем с начального состояния I, затем вычисляем все переходы, которые начинаются из I, затем снова начинаем с новыми полученными состояниями и т. д.

NB: метод курса также действителен для учебных пособий и проекта. Вы используете тот, который вы понимаете лучше всего! У вас есть тот же пример с нотациями курса после этого метода.

исходное состояние: I = {1} переход по a: {1, 2} переход по b: {1} . Мы только что сделали {1}, так что мы сделаем {1,2}

состояние {1, 2} переход на a: {1, 2} переход на b: {1, 3}, теперь мы делаем {1,3}

переход состояния {1, 3} по a: {1, 2} переход по b: {1}. Непосещенных штатов не осталось. Только состояние {1,3} содержит терминальное состояние, поэтому {1,3} является терминальным.

Что дает нам следующий DFA:

AFI в AFD

Расчет по таблицам намного читабельнее.

дельтавб
1{1,2}{1}
2{3}
3

Давайте посчитаем дельта-простые состояния:

Детла премиумвб
1{1,2}1
1,2{1,2}{1,3}
{1,3}{1,2}{1}

Вторая строка создает для нас состояние {1,3}. Мы замечаем, что в конце автомат такой же, как и тот, который был рассчитан предыдущим методом (состояние 3 бесполезно, так как его никто не вызывает).

Делиться
ru_RURU