CFG to PDA (Контекстная свободная грамматика для толкания автоматов)

Question

Как я могу конвертировать следующий CFG в КПК?

S-> abScB | e 

B-> bB | b 

Answer 1

Сначала я бы посмотрел на язык, который генерирует CFG. На самом деле это довольно сложный язык. Только с одним расширением S будет abc(b(b*)). Для двоих вы получите ab[abc(b(b*))]c(b(b*)), три будут ab[ab[abc(b(b*))]c(b(b*))]c(b(b*)) и так далее. Я поставил квадратные скобки часть, добавленную из S-перехода. Этот язык представляется {(ab)^n (c(b(b^x_i)))^m}, где x_i - целое число, большее или равное 0, и каждый x_1, x_2, ... , x_i может быть другим. п и м является целыми числами больше или равно 0.

Для преобразования в КПК, мы можем начать с легкими частями. Ваш алфавит будет {a, b, c}, вам понадобится состояние для раздела «ab», а другое - для части «c (b (b^x_i)». Назовем первое одно состояние p и второй q. Ваш алфавит стека будет {bottom, A, C}. Внизу просто символ, который указывает, что мы достигли дна стека. Теперь сложная часть, дельта-переходы, предполагающая принятие пустым стеком :.

(p,e,bottom),(p,e) - this is for "m" = 0, accepting the empty string "e" or the case (ab)^n (this is an accepting state) 
(p,a,bottom),(p, A bottom) - if we read an "a" and the stack is empty, push an A to the stack 
(p,b,A),(p,e) - if we get a "b" and there was already an A on the stack, remove it 
(p,c,bottom),(q,C bottom) - if we get a "c" and the stack was empty (i.e. we've finished the (ab)^n section), go to state q and push a C onto the stack 
(q,b,C),(q,e) - if we get a "b" after a c, remove the C from the stack 
(q,b,bottom),(q,bottom) - if we get a "b" in the b^x_i section, pop then immediately push bottom onto the stack 
(q,c,bottom),(q,C bottom) - if we get a "c" after the b^x_i section, push a C onto the stack 
(q,e,bottom),(q,e) - if we finish our string and our stack is empty (as it should be), then this is an accepting state 

вышеуказанных переходы, которые читают пустую строку и продуцируют пустую стек являются принимающими государствами всех переходов, которые не разрешены (например, получение «с», когда уже есть C в стеке) не включены.

Надеюсь, что это поможет!