Как получить контекстно-свободную грамматику и соответствующий ей КПК? - PullRequest
Новая
       55

Как получить контекстно-свободную грамматику и соответствующий ей КПК?

1 голос
/ 15 января 2012

Я не могу понять, как я могу решить это упражнение.

Мне нужно создать контекстно-свободную грамматику, которая может проверять следующий ввод: 

L={w € (0,1,2)* | w= 2^n 0^(m+1) 1^(m+n) with n>=0, m>0}

Как мне создать соответствующий КПК?

Я думаю, что у языка нет префиксного свойства, поэтому КПК не может принимать пустой стек. Это правильно?

1 Ответ

2 голосов
/ 16 января 2012

Давайте сначала попробуем грамматику;тогда мы сделаем для него автомат.

При создании CFG - любой грамматики, в том числе регулярных выражений - полезно знать несколько видов простых языков, которые грамматика могла бы легко сделать.Контекстно-свободные грамматики могут довольно легко делать все, что может делать обычная грамматика, и могут также соответствовать входным данным.Это означает, что такие языки, как ^ nb ^ n, палиндромы, совпавшие скобки и т. Д. Легко сделать.

При рассмотрении проблемы, подобной этой, попытайтесь увидеть, какой из этих стереотипных языков, если таковые имеются, все иличасть строк на вашем языке выглядит так.В этом случае оказывается, что у нас есть вариация на ^ nb ^ n;нам нужно сделать это дважды, чтобы выполнить сложение.

Давайте начнем с 0 ^ (m + 1) 1 ^ m.Можем ли мы сделать CFG для этого?Хорошо обязательно;это практически так же, как ^ NB ^ N.Вот оно: 

S := 0E
E := 0E1 | -

Теперь нам нужно обратиться к n-члену: мы должны иметь возможность добавить 2 слева и 1 справа равным числом.Это также легко: 

S := 2S1 | S'
S' := 0E
E := 0E1 | -

Вот, пожалуйста.Чтобы получить CFG, вы можете легко создать анализатор снизу вверх или сверху вниз, в соответствии с определением этих вещей.Мы попытаемся сделать КПК с нуля.

Наш КПК должен принимать 2 в цикле, помещая каждые 2 в стек.Нам нужно будет вспомнить, сколько мы видели, в конце концов.Когда мы видим 0, мы должны перейти в новое состояние и продолжать принимать 0 в цикле, добавляя 0 в стек для каждого 0, видимого на входе.Когда мы видим 1, мы должны перейти в новое состояние и принять 1 в цикле, удаляя либо 2, либо 0 из стека.Если вы правильно укажете детали реализации, вы сможете принять с пустым стеком в состоянии принятия отдельно от первых трех.

...