Исключение тупиковых правил из грамматик

Правило A® j By называется внешним тупиком, если не существует правила B®x . (Из нетерминала B нет выхода).

Правило B® x называется внутренним тупиком, если B ¹ S и не существует правила A® j By. (Нетерминал B не может появиться ни в одной сентенциальной форме, выводимой из начального символа грамматики. Внутренний тупик - это аналог недостижимого состояния конечного автомата).

Циклический тупик - это группа правил вида

A₀® j₁A₁y₁

A₁® j₂A₂y₂

..................

A_n® j₀A₀y₀ ,

где A_i ¹ S и при этом либо для любого A_i не существует правил вида B® lA_im (циклический тупик внутреннего типа), либо для любого A_i не существует правил вида A_i®c (циклический тупик внешнего типа). ƒ

Теорема 4.5. Для любой грамматики существует эквивалентная ей грамматика без тупиков.

Для доказательства данной теоремы достаточно вспомнить, что эквивалентные грамматики порождают один и тот же язык (множество терминальных цепочек, которое выводятся из начального символа грамматики). Очевидно, что правила, включающие тупики, при порождении терминальных цепочек из начального символа грамматики просто не могут использоваться.

Алгоритмы поиска тупиков и их устранения рассмотрим на примере.

Пример 4.4. Пусть задана грамматика c начальным символом S и следующим множеством правил

S® a A½c C½b D½q P½k T A® c C

C® k T® m

D® b T½f K P® c R

R® d K B® d Q½m

Q® p B½r B.

Здесь выбрана автоматная грамматика только для того, чтобы наглядно проиллюстрировать ее графом состояний (рис. 4.1).

Построим новую грамматику, отбирая из исходной “хорошие” (производящие нетерминалы), из которых выводится терминальная цепочка.

Для этого положим, что множество X₀ = V_T ,

_,то есть X₀ совпадает с множеством терминалов.

X₁ = { A | $ A® x , где xÎ X_o} ,

то есть те нетерминалы, из которых терминальная цепочка получается за один шаг.

X₂ = { A | $ A® x , где xÎ ( X_o È X₁ ) } ,

.......................................................

X_i = { A | $ A® x , где xÎ } ,

то есть X_i - множество нетерминалов, из которых терминальная цепочка получается не более, чем за i шагов (под шагом здесь понимается одновременная замена всех нетерминалов сентенциальной формы). На каждом шаге мы добавляем новые нетерминалы, их конечное число, следовательно конечен и данный процесс ( X₁ Í X₂ Í ... X _i Í V_N ).

Положим Z _i равным разности X _i и X _i-1 ,Z _i = X _i \ X _i-1 - это те нетерминалы, из которых терминальная цепочка получается ровно за i шагов. Если Z _i = Æ, - пустое множество, то процесс формирования продуктивных нетерминалов пора закончить, так как из Z _i = Æ следует, что Z _i+1 = Æ и т.д.

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

В рассматриваемом примере

X₀ = {a,c,b,q,k,m,f,d,p,r},

X₁ = {C,T,B}, Z₁ = {C,T,B},

X₂ = {S,A,C,T,D,Q,B}, Z₂ = {S,A,D,Q}

X₃ = {S,A,C,T,D,Q,B}, Z₃ = Æ.

Следовательно X₃ и есть то самое множество “хороших” нетерминалов. Удалив остальные нетерминалы и все ссылки на них в правилах грамматики, мы получим грамматику:

S® a A½c C½b D½k T A® c C

C® k T® m

D® b T B® d Q½m

Q® p B½r B.

Для устранения внутренних тупиков повторим процесс выбора “хороших” символов с другого конца. Положим

Y₀ = { S }, ... , Y _i = { A | $ B® jAy, где AÎ ( V_TÈ V_N) и BÎ Y _i-1 },

то есть Y _i - множество символов (терминалов и нетерминалов), которые могут появиться в сентенциальной форме на i - том шаге вывода.

В нашем примере

Y₀ = {S},

Y₁ = {a,A,c,C,b,D,k,T},

Y₂ = {c,C,k,m,b,T}, Y₃ = {k,l}.

Далее определим W _i = Y _i \ ( ) Ç V_N, то есть новые нетерминалы, появляющиеся на i - том шаге. Очевидно, что из W _i = Æ, следует что процесс можно закончить, так как все нетерминалы, выводимые из начального символа грамматики, уже получены. Остальные нетерминалы и содержащие их правила грамматики можно удалить.

В нашем случае

W₀={S},

W₁={A,C,D,T},

W₂=Æ.

Нетерминалы B и Q - внутренние тупики. Таким образом, грамматика без тупиков имеет вид:

S® a A½c C½b D½k T A® c C

C® k T® m D® b T .