Как вы получаете переходные отношения КПК?

Question

Я знаю, как определить начальное состояние, принимаемое состояние, входной алфавит и все такое. Но как вы развиваете переходные отношения КПК? Для FSM (q0,a),q1) означает, что если вы начинаете с q0 и получаете a, вы переходите к q1. Но что означает (S, a, e), (S, a)? (S - начальное состояние и e - эпсилон)

Answer 1

Вместо эпсилона в (S,a,e),(S,a) это должен быть нижний символ (выглядит как перевернутая буква T). Я объясню это немного позже.

Первый S - это просто состояние, в котором вы сейчас находитесь. Это соответствует q0 в FSM.

A - это символ, который вы прочитали, такой же, как a в FSM. Обратите внимание, что когда вы получаете e вместо a, что означает, что вы находитесь в конце своей строки, больше нечего читать.

Основное отличие заключается в следующей букве, в данном случае в e. Это обозначает одиночный символ стека, который находится на вершине стека, когда вы читаете свой a. Технически вы никогда не сможете прочитать пустой стек, хотя. В компьютерах это то же самое, что чтение нулевой памяти, но это просто невозможно. Это потому, что "низ" стека содержит один символ, который говорит, что вы внизу. Традиционно это выражается с помощью перевернутой буквы T (нижний символ).

S во второй скобке обозначает состояние, в которое вы собираетесь, точно так же, как q1 в FSM.

И, наконец, буква a во второй скобке - это символ (или символы), который вы хотите добавить в стек. Каждый раз, когда вы что-то читаете из стека (что происходит каждый раз, когда происходит переход), этот символ удаляется из стека. Затем вы можете положить новый символ или несколько новых символов в стек или ничего не помещать (e). Ничего не ставить, когда вы только что прочитали нижний символ, означает, что вы сделали, и вы принимаете строку (если принимаете пустым стеком). Вы также можете принять по окончательному состоянию, но пустой стек немного проще.

Я покажу вам быстрый пример, КПК для {a^n b^n | n >= 0}. Наш алфавит, очевидно, {a,b}, нам понадобятся 2 состояния (одно для раздела a и одно для раздела b), назовем их {p,q}. Мы позволим p быть нашим начальным состоянием. Наш алфавит стека, символы, которые мы можем поместить в стек, будет {bottom,A}. Нижняя часть всегда является частью алфавита стека, и мы будем помещать A в стек каждый раз, когда получаем a (и выталкивать каждый раз, когда получаем b). Давайте примем пустой стек, что означает, что когда мы читаем e как символ, а bottom как символ стека, если мы ничего не кладем обратно в стек, то мы принимаем эту строку. Наши дельта-переходы следующие:

(p,e,bottom),(p,e) //this is an accepting state for a^0 b^0
(p,a,bottom),(p,A bottom) //we read an a and we're at the bottom of the stack, we add an A to the stack and put back the bottom symbol below it.
(p,a,A),(p,AA) //we read an A off the stack and an *a* in our string, we put back the A we read from the stack and add another one
(p,b,A),(q,e) //we read an A off the stack and a *b*, so we go to our state q, and don't add anything to the stack.
(q,b,A),(q,e) //every time we get a *b* and there's an A on the stack, remove it
(q,e,bottom),(q,e) //this is an accepting state, as we've canceled out all the a's with b's and we're done reading our string.

Обратите внимание, что есть переходы, которые не разрешены, такие как получение b перед любым a. Не включая их, строки, которые требуют их, не принимаются. Надеюсь это поможет!