Давайте не будем сразу переходить к разработке КПК для этой проблемы, а попробуем сначала понять вопрос.
Какие несколько возможных строк могут быть сгенерированы на данном языке.
Ну, можетбыть бесконечной такой строкой, например -
- aab
- aaab
- aaa ... b
- aaaa..bb
Идея состоит в том, чтобы убедиться, что число a всегда больше, чем число b, или мы можем сказать, что число b в строке никогда не должно превышать количество a в строке, которая будет принята КПК.
Итак, теперь у нас есть вопрос.
Как убедиться, что число a больше, чем число b
Для строки, если мы начнем отменить a для каждого 'b' в строке
Нам останется следующий вывод
- Число a было равно количеству b - После отмены ничего не осталось
- Количество b было больше чем numчисло а - у нас осталось несколько б после отмены
- число а было больше числа б - у нас осталось несколько а после отмены
Если мы попытаемся установить связь между «Вопросом» и указанными выше точками, мы увидим, что строки, принадлежащие вышеуказанной точке № 3, являются строками, приемлемыми для КПК.
Теперь давайте определим наш КПКследующим образом
P = ({q0, q1, qf}, {a, b}, δ, {a, b, Z0}, q0, Z0, {qf})
Функция перехода (δ):
δ(q0, a, Z0) = (q0,aZ0)
δ(q0, a, a) = (q0, aa)
δ(q0, b, a) = (q1, Λ)
δ(q1, b, a) = (q1, Λ)
δ(q1, Λ, a) = (qf, Z0)
δ(q1, b, Z0) = (q2, Z0)
δ(q1, Λ, Z0) = (q2, Z0)
Объяснение:
- Первоначально мы храним a в стеке (состояние q0)
- Когда первыйb встречается, мы извлекаем a из стека и меняем состояние на q1
- Мы продолжаем извлекать a из стека
- Если не осталось b для извлечения a из стека, мы меняем состояние на qf науказать строку принятия. (ТОЧКА № 3)
- Если осталось немного b, но нет a, чтобы выскочить из стека, мы меняем состояние с q1 на q2 (Trap). (ТОЧКА № 2)
- Если ни a не осталось в стеке, чтобы выскочить, либо b не осталось во входной строке, мы снова изменим состояние с q1 на q2 (Trap). (ТОЧКА № 1)