Принятие автоматов выталкивания

Есть два разных способа определить приемлемость КПК.

Приемлемость в конечном состоянии

В допустимости конечного состояния КПК принимает строку, когда после прочтения всей строки КПК находится в конечном состоянии. Из начального состояния мы можем делать ходы, которые заканчиваются в конечном состоянии с любыми значениями стека. Значения стека не имеют значения, пока мы находимся в конечном состоянии.

Для КПК (Q, ∑, S, δ, q 0 , I, F) язык, принятый набором конечных состояний F, -

L (КПК) = {w | (q 0 , w, I) ⊢ * (q, ε, x), q ∈ F}

для любой строки стека ввода x.

Приемлемость пустого стека

Здесь КПК принимает строку, когда после прочтения всей строки КПК опустошает свой стек.

Для КПК (Q, ∑, S, δ, q 0 , I, F) язык, принимаемый пустым стеком, -

L (КПК) = {w | (q 0 , w, I) ⊢ * (q, ε, ε), q ∈ Q}

пример

Создайте КПК, который принимает L = {0n 1n | n ≥ 0}

Решение

Этот язык принимает L = {ε, 01, 0011, 000111, .............................}

Здесь, в этом примере, количество ‘a’ а также ‘b’ должно быть таким же.

  • Изначально ставим специальный символ ‘$’ в пустую стопку.

  • Тогда в состоянии q2, если мы сталкиваемся с входом 0 и вершиной является Null, мы помещаем 0 в стек. Это может повторяться. И если мы сталкиваемся с входом 1 и вершиной является 0, мы выталкиваем этот 0.

  • Тогда в состоянии q3, если мы сталкиваемся с входом 1 и вершиной является 0, мы выталкиваем это значение 0. Это также может повторяться. И если мы сталкиваемся с входом 1 и top равным 0, мы выталкиваем верхний элемент.

  • Если в верхней части стека встречается специальный символ «$», он выскакивает и, наконец, переходит в состояние приема q 4 .

пример

Создайте КПК, который принимает L = {ww R | w = (a + b) *}

Solution

Сначала мы помещаем в пустой стек специальный символ «$». В состоянииq2, то wчитается. В состоянииq3, каждый 0 или 1 появляется, когда он соответствует вводу. Если подан какой-либо другой ввод, КПК перейдет в мертвое состояние. Когда мы достигаем этого специального символа '$', мы переходим в состояние принятия.q4.