Дизайн «Push Down Automata», который распознает язык: a ^ nb ^ m |n <= m <= 3n

Question

Я готовлюсь к экзаменационным автоматам и формальным языкам, мне нужно разработать КПК, который распознает язык:

a^n b^m | n<= m <= 3n

У меня есть небольшая идея, но я застрял с этим:

сначала мыслительный процесс все «а» и каждый «а» толкают «А»

(q0, a, Z)= (q0, AZ)
(q0, a, A)= (q0, AA)
(q0, b, A)= (q1, A)
(q1, b, A)= (q2, A)
(q2, b, A)= (q3, lambda)
(q3, b, A)= (q1, A)
(q3, lambda, A)= (qf, Z)
(q3, lambda, Z)= (qf, Z)

qf = final state, lambda= delete top of stack, Z= initial symbol of the stack

Так я думал, что решение, но я думаю, что это не правильно, я делаю что-то не так?

Answer 1

Да, ваш автомат не прав, так как он не принимает строку ab или пустую строку в этом отношении.Вы получаете следующие последовательности состояний машины:

- q0 Z
a q0 AZ
b q1 AZ
(doesn't accept)

- q0 Z
(doesn't accept)

Поскольку q1 не принимает, ваша машина не может принять ab, то есть на языке, который вы описываете.

У вас есть правоОбщая идея: добавьте A для каждого a, который вы видите, а затем удалите A для каждой группы из 1, 2 или 3 b, которые вы видите.Эта формулировка явно недетерминирована, но мы будем считать, что это нормально, если только DPDA не запрашивается.

(q0, a, Z) => (q0, AZ)
(q0, a, A) => (q0, AA)
(q0, -, Z) => (q1, Z)
(q0, -, A) => (q1, A)

Эти переходы подсчитывают a и добавляют A в стек.Когда вы закончите читать a, мы можем перейти к следующему состоянию, q1, и начать считать b и выталкивать буквы A.

(q1, -, A) => (q2, A)
(q1, -, A) => (q3, A)
(q1, -, A) => (q4, A)

Эти переходы позволяют машине недетерминированно выбирать, считать ли один, два,или три b для конкретного A.

(q2, b, A) => (q1, -)

(q3, b, A) => (q5, A)
(q5, b, A) => (q1, -)

(q4, b, A) => (q6, A)
(q6, b, A) => (q7, A)
(q7, b, A) => (q1, -)

Эти переходы фактически обрабатывают подсчет одного, двух или трех b и удаление A, возвращаясь к q1, чтобы позволить удаление дополнительных A из стека.

(q1, -, Z) => (qf, Z)

Этот переход позволяет КПК принимать строки после того, как стек A исчерпан.Обратите внимание, что если на входе остаются какие-либо b, КПК будет зависать в qf, поскольку там не определены переходы;и так как он аварийно завершает работу, строка не принимается (даже если стек пуст и происходит сбой в состоянии принятия).

Другой подход к этой проблеме - создать CFG для этого языка, а затем создатьпарсер сверху вниз или снизу вверх.Простой язык CFG для этого языка:

S := aSb | aSbb | aSbbb

Если требуется DPDA, это более сложная проблема, и ответ на нее может быть «DPDA не существует».Если честно, я не задумывался над созданием DPDA для этого языка.

Answer 2

я знаю, что это немного поздно, но я столкнулся с той же проблемой, и я подумал, если другое решение, поэтому основная идея состоит в том, что вы разбиваете свой стек на 3 раздела со следующими свойствами

• первый раздел: (размер = n, символ = 'A')
• второй раздел: (размер = 2n, символ = 'B')
• третий раздел: (размер = n, символ = 'A')

самый верхний раздел - третий - его цель состоит в том, чтобы удостовериться, что счетчик b, по крайней мере, равен счету a -n-, средний раздел - второй - чтобы убедиться, что счетчик b меньше или равен 2n, последний раздел должен убедиться, что число b не превышает 2n; так что это основная идея, и, конечно, это NPDA, вот точные переходы:

(q0 , a , #) => (q0 , A#)
(q0 , a , A) => (q0 , AA)
(q0 , a , B) => (q0 , AB)
(q0 , b , A) => (q0 , BA)
(q0 , b , B) => (q0 , BB)
(q0 , lambda , A) => (q0 , AA)
(q0 , lambda , B) => (q0 , AB)
(q0 , lambda , B) => (q0 , BB)
(q0 , lambda , A) => (q0 , BA)
(q0 , b , A) => (q1 , match) >> -match means removing the top of the stack with the current element-

Теперь мы переходим к q1, чтобы убедиться, что число b, по крайней мере, равно числу a:

(q1 , b , A) => (q1 , match)
(q1 , # , B) => (qf , -) >> -this means that i matched equal number of a's and b's and i can halt if there is no more input-
(q1 , b , B) => (q2 , match)

Теперь мы переходим к q2, чтобы убедиться, что число b меньше или равно 2n:

(q2 , b , B) => (q2 , match)
(q2 , # , A) => (qf , -)
(q2 , # , B) => (qf , -)