НПД для языкового числа а меньше или равно в 3 раза больше числа б

Я пытаюсь построить НПД для L = {w ∈ {a, b} * | n a (w) <= 3 * n b (w)}. Это означает, что для каждого b может быть не более 3 a.

Прежде всего, это то, что я сделал до сих пор. Из начального состояния мы помещаем один " a " в стек. (в конце дня нам нужно увидеть это " а ", чтобы добраться до конечного состояния, если бы было больше 3 а для каждого b, мы бы вытолкнули это " а ", и мы бы не достигли финала государство).

Тогда для каждого b в строке я бы нажал 3 a. Для каждого а на входе я бы выбил один " а ".

В конце, если в стеке есть a, мы переходим в конечное состояние.

Нажмите здесь для рисунка NPDA

Итак, давайте рассмотрим строку, где nb(w)= 1 и na(w) = 3. У нас может быть строка типа baaa, aaab, abaa, aaba. (есть и другие)

Если бы мы запустили нпда за бааа. Это будет работать нормально.

Ничего не читая (лямбда) мы нажимаем. Затем мы читаем б и нажимаем ааа. Содержимое стека (аааа). Затем мы читаем и выкладываем сингл. Мы делаем это 3 раза, и стек становится (а). После прочтения строки в стеке остается левый элемент, поэтому мы можем перейти в конечное состояние.

Проблема заключается в том, что эта конструкция работает только тогда, когда b поставляет 3 a в стек сначала в избытке, прежде чем a появится в строке. Если мы запустим npda в строке aaab, это больше не будет работать. У нас будет один a в стеке, читая первый a, который мы должны вытолкнуть a. Чтение второго а, никакая операция не может быть сделана. В стеке ничего нет, и мы не можем нажать a, потому что это все испортит.

Как я мог бы исправить эту конструкцию или есть лучшая конструкция npda для языка.

Я работал над этим в течение нескольких дней. Помощь будет принята с благодарностью.

Также знайте, что я очень новичок в npda, поэтому может случиться так, что я делаю что-то, что в корне неправильно. Так что будьте понятны в объяснении.

Спасибо

Источник

2 ответа

Решение

Не уверен, что смогу дать вам точный ответ, потому что уверен, что мы в одном классе 335. лол.

Основная проблема заключается в том, что вы не учитываете все возможности.

Начальное состояние имеет 14 возможностей в своем цикле, и оно может разветвляться на 2 ветви, которые возвращаются в исходное состояние. Он также имеет переход в конечное состояние после просмотра символа конца стека.

Все это, за исключением отмеченных, выполняется в цикле начального состояния.

Увидев:

a input:
    Push a onto the stack

b input:
    You can pop it or replace it with 1 or 2 b's
    Or
    You can pop one b
    Or
    You can pop 2 or 3 b's (Done by branching into 2 different branches of
    states that do just that, respectively, and return to the initial state)

Увидев б:

a input:
    Pop b (Only way to meet criteria for final state)

b input:
    Push 0 to 3 b's

Увидев символ конца стека:

empty string input:
    Go to final state.

Я мог бы помочь больше, если бы у меня было другое средство общения.

Источник

Хорошо, вот подсказка. Пока что ваше решение в основном заключается в использовании стека в качестве счетчика для вычисления значения 3*nb(w) - na(w) при сканировании строки с использованием глубины стека в качестве значения счетчика. На "б" вы добавляете 3, а на "а" вы вычитаете один. В принципе, хорошее решение.

Проблема в том, что это работает только до тех пор, пока счетчик никогда не станет отрицательным. Чтобы он работал во всех случаях, вам нужно, чтобы ваш счетчик записывал отрицательное число. Подумайте, как вы могли бы использовать стек в качестве счетчика, который мог бы легко записать положительное или отрицательное число, и сказать вам, если конечное значение>= 0 в конце...

Источник
Другие вопросы по тегам