Скачать или смотреть Недетерминированный КПК NDPDA || Урок 74 || Конечные автоматы || Обучение обезьяны ||

Недетерминированный PDA NDPDA
В этом курсе мы обсудим недетерминированный PDA NDPDA.
Читатель должен иметь предварительные знания о детерминированных автоматах с магазинной памятью. Нажмите здесь.
Недетерминированный автомат с магазинной памятью: автомат с магазинной памятью считается недетерминированным, если один переход может выполнять более одного хода.
Мы можем достичь NDPDA двумя способами.
а) если два ребра имеют одинаковый вход и стековый символ из состояния.
На диаграмме ниже показан первый случай.
б) Когда в состоянии два ребра имеют одинаковый входной символ и один входной символ — эпсилон.
На диаграмме ниже показан второй случай.
Теперь мы разработаем несколько примеров с использованием недетерминированных автоматов с магазинной памятью.
Пример 1: Возьмём язык L1 = {ww^R, где w — это строка длиной больше нуля.
Строки в языке L1 = {abba, abbbba, . . .}
Логика немного сложна для понимания. Читателю следует сосредоточиться на этом.
Читатель должен понимать NFA. Нажмите здесь.
Возьмём входную строку abbbba.
Первый символ — a. Мы помещаем его в стек.
Второй символ — b. Теперь нам нужно выполнить проверку двумя способами.
Из середины входной строки нам нужно проверить перевёрнутость строки.
Сложность здесь в том, как определить середину строки?
Поэтому мы предполагаем, что каждый входной символ со второй позиции является серединой строки, и применяем логику операции извлечения.
Вторая логика заключается в том, чтобы предположить, что входной символ не находится в середине строки, и применять логику операции извлечения.
Исходя из идеи недетерминизма, один PDA будет двигаться вперёд и проверять логику операции извлечения.
Другой PDA останется в том же состоянии и применит логику операции извлечения.
После окончания входной строки один из PDA выполнит успешное выполнение. Мы применяем NDPDA описанным выше способом.
На диаграмме ниже показан полный NDPDA для языка L1.

Ссылка на плейлисты:
   / @wisdomerscse  

Ссылка на наш сайт: https://learningmonkey.in

Подпишитесь на нас в Facebook:   / learningmonkey  

Подпишитесь на нас в Instagram:   / learningmonkey1  

Подпишитесь на нас в Twitter:   / _learningmonkey  

Напишите нам: [email protected]