Принятие автоматов выталкивания
Есть два разных способа определить приемлемость КПК.
Приемлемость в конечном состоянии
В допустимости конечного состояния КПК принимает строку, когда после прочтения всей строки КПК находится в конечном состоянии. Из начального состояния мы можем делать ходы, которые заканчиваются в конечном состоянии с любыми значениями стека. Значения стека не имеют значения, пока мы находимся в конечном состоянии.
Для КПК (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.