Вопрос 6. Лемма о виде продукции формальных грамматик. Теорема об е-свободной КС-грамматике.
Грамматики свободные от пустой строки или e-свободные грамматики.
Лемма: Для любой грамматики G , содержащей e (пустую строку) в своих продукциях возможны только продукции вида ?G : e ? p ; ??e ; ? ? (V?W)+ .
Предположим, что существует продукция содержащая e : ?1 e ?2 ? ?1 e ?2 ; где ?1,?2 ,?1 ,?2 ?(V?W)+ ; ?1 ?2 ? ?1 ?2 следовательно e не может быть подстрокой.
Рассмотрим другой вариант : e ? ?1 ?2 , ?1 , ?2 ? e , ? является единственно возможной.
Грамматика свободная от пустой строки, называется грамматика в которой отсутствует продукция вида ??e ; где ? ? (V?W)+ .
Замечание. Грамматики типа 1, контекстные, называют не укорачивающими, что не всегда верно. Действительно, по определению контекстной грамматики, продукции которой имеют вид ? A ? ? ? ? ? , где ?, ?, ? ? (V?W)*, видно, что контекстная грамматика допускает продукцию с пустой строкой, но в этом случае она является укорачивающей.
Грамматика называется неукорачивающей, если | ? A ? | ? | ? ? ? |. В связи с тем, что множество грамматик большого типа являются подмножеством грамматик меньшего типа, то в определении контекстной грамматики мы должны потребовать, чтобы ? = e. Таким образом, не каждая контекстная грамматика является неукорачивающей.
Замечание. Наличие у КС-грамматик e-продукции ( ?? e … ), осложняет использование грамматик для описания языка и реализации автоматов порождающих и распознающих этот язык.
Теорема 1.3. (О существовании КС-грамматики без e-продукции.) Для любого языка порожденного КС-грамматикой ? (G2 ) , существует e-свободная КС-грамматика G2| , такая что L (G2| ) = L ( G2 ) \ {e}.
Шаг 1. Находим все e-продукции и помещаем их в множество продукций P| , удаляя их из множества P. P| = {? ? e | ? ? (V?W)+ }, P| ? P , P|| = P \ P| .
Шаг 2. Каждой продукции из P|| поставим в соответствие (заменим) на продукции, в которых опущены один или более e-порождающих нетерминальных знаков.
Шаг 3. Если полученная система продукций P|| не содержит e-продукции, то завершим построение, а иначе переходим к шагу 1.
Замечание 1. На практике в множество P| удобно выделять по одной продукции, а не все сразу.
Замечание 2. Из примера видно, что если e ? L ( G2 ) , то грамматика G2 может быть эквивалентно преобразована в грамматику G2| , ( G2 ? G2| (I ? e)) , содержащую единственную пустую продукцию, из аксиомы выводится пустая строка.
Замечание 3. Теорема 1.3. дает эффективную процедуру позволяющей избавиться в грамматике любого типа от пустых продукций (заменять разрешается только в правой части продукции).