Приведите пример другой грамматики, задающей тот же язык.

Ответ. Вот один из вариантов:

<выр> -> <выр> + <выр> <выр> -> <выр> * <выр> <выр> -> x <выр> -> ( <выр> )

Эта грамматика хоть и проще, но в некоторых отношениях хуже, о чем мы еще будем говорить.

Дана произвольная КС-грамматика. Построить алгоритм проверки принадлежности задаваемому ей языку, работающий полиномиальное время (т.е. число действий не превосходит полинома от длины проверяемого слова; полином может зависеть от грамматики).

Решение. Заметим, что требование полиномиальности исключает возможность решения, основанном на переборе всех возможных выводов. Тем не менее полиномиальный алгоритм существует. Поскольку практического значения он не имеет (используемые на практике КС-грамматики обладают дополнительными свойствами, позволяющими строить более эффективные алгоритмы), мы изложим лишь общую схему решения.

(1) Пусть в грамматике есть нетерминалы K1,...,Kn. Построим новую грамматику с нетерминалами K1',...,Kn' так, чтобы выполнялось такое свойство: из Ki' выводятся (в новой грамматике) те же слова, что из Ki в старой, за исключением пустого слова, которое не выводится.

Чтобы выполнить такое преобразование грамматики, надо выяснить, из каких нетерминалов исходной грамматики выводится пустое слово, а затем каждое правило заменить на совокупность правил, получающихся, если в правой части опустить какие-либо из нетерминалов, из которых выводится пустое слово, а у остальных поставить штрихи. Например, если в исходной грамматике было правило

K -> L M N,