Преобразование КПК в CFG

Question

Я пытаюсь понять этот пример преобразования КПК в CFG, но я не понимаю идею совершенно правильно. У меня есть общее понимание теоремы, что если $ p, q \ \ epsilon \ Q $ и $ x \ varepsilon \ \ Gamma $ для $ [pxq] $ У нас есть последовательность производных, которые бы поп- x из стека.

Я частично понимаю, что происходит, но я не могу понять, как развернуть производства, чтобы сформировать строки, чтобы я мог понять это ясно. Возьмите производство (5) в примере. Из того, что я понимаю, мы находимся в состоянии P, мы хотим поп-а и в конце концов, мы должны быть в состоянии P с пустым стеком. Как мы читаем 0 , у нас есть ноль в производстве, за которым следует $ [PAQ] [QAP] $ , это то, что я есть Не понимая, потому что если мы посмотрим на КПК, нет способа перейти к чтению 0. Я хотел бы знать, что на самом деле происходит.

связанный вопрос отвечает Здесь Но я не могу понять это, как очистить мою путаницу.

Answer 1

У вас есть базовая интуиция права. Переменная $ [p, a, q] $ представляет набор (строки, принимаемые) вычисления из состояния $ P $ Для состояния $ Q $ , который будет поп-главный символ $ A $ из стека.

Технические характеристики отношения между грамматикой $ G $ и PDA $ m $ дается на вершине слайд вы показываете.

Тогда конструкция следует рекурсию. Если PDA POPS $ a $ но толкает $ B_1B_2B3 $ Грамматика заменит вычисление на <класс SPAN= «Математический контейнер»> $ a $ начиная с $ p $ и заканчивая $ Q $ < / span> на три отдельных вычисления $ [Q_1, b_1, q_2] [q_2, b_1, q_3] [q_3, b_1, q] $ . Здесь промежуточные состояния $ q_2, q_3 $ неизвестны и находятся в угадают грамматику. Только $ Q_1 $ известен, так как это состояние, в котором инструкция PDA перемещается.

Ваше наблюдение правильно. Эта стандартная конструкция может ввести триплет $ [P, A, Q] $ , который будет бесполезным. В вашем примере не будет вычислений от $ q $ на $ P $ TO THE TROUTLE $ [Q, A, P] $ никогда не используется в успешном выводе. Это несовнамерен. Строительство просто производит все возможности, а переменные, которые оказываются бесполезными, могут быть удалены впоследствии, если кто-то действительно хочет.

Примечание. Другой вопрос, который вы ссылаетесь, чтобы использовать другую модель автоматов стиля SPOSSER! Там символы стека нажимаются один за другим, не поднимаясь одновременно. Чтобы добавить в путаницу Ta href="https://cs.stackexchange.com/a/51676/4287"> Ответить , учитывая на этом вопросе, отлично соответствует конструкции с вашего слайда!