УДАЛЕНИЕ БЕСПОЛЕЗНЫХ СИМВОЛОВ ГРАММАТИКИ

ПРОВЕРКА СУЩЕСТВОВАНИЯ ЯЗЫКА

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

Обозначим N= {Z | ZÎN, ZÞ*x, xÎT} и рассмотрим алгоритм проверки существования языка.

Вход: КС-грамматика G=(N, T, P, S)

1. Положить N₀=Æ

2. Вычислить N₁= N₀ È {A | (A®a) Î P и a Î (N₀ È T)*}

3. Если N₁¹ N₀ , то положить N₀= N₁ и перейти к п.2; иначе положить N= N₁

4. Если SÎN, то язык существует, иначе язык не существует

Пример.Язык, определяемый грамматикой с правилами

1) S® AB 2) A ® aA 3) A ® a 4) B ® b

не пуст, что подтверждает результат применения изложенного алгоритма.

1. N₀=Æ

2. N₁={A, B}

3. N₁= N₀ ? Нет N₀ = N₁={A, B}

4. N₁={A, B, S}

5. N₁= N₀ ? Нет N₀ = N₁={A, B, S}

6. N₁={A, B, S}

7. N₁= N₀ ? Да N = N₁={A, B, S}

5. SÎN то L(G) =Æ, т.е. язык существует

При разработке грамматики языка могут возникнуть следующие ошибки:

§ В грамматике имеются нетерминальные символы, которые не участвуют в выводе терминальных цепочек

§ В грамматике существуют символы, недоступные из начального символа грамматики

Бесполезные символы это

W={X | X Î S, Ø$(SÞ*aXbÞ*axb, a, x, b Î T*).

Их можно разделить на три группы:

8.2.1.1 нетерминалы, не порождающие терминальных строк

{X | X ÎN, Ø$(XÞ*x), x Î T*}

8.2.1.2 недостижимые нетерминалы, порождающие терминальные строки

{X | X Î N, Ø$(SÞ*aXb), $(XÞ*x), a, b Î S, xÎT).

8.2.1.3 недостижимые терминалы

{X | X Î T, Ø$(SÞ*aXb), a, b Î S).

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

Алгоритм устранения нетерминалов, не порождающих терминальных строк, состоит в следующем:

Вход: КС-грамматика G=(V_N, T, P, S) без e-правил.

Выход: Эквивалентная КС-грамматика G’=(V_N, T, P’, S) у которой L(G)=L(G’) и для всех Z Î N существуют выводы ZÞ*x, где xÎT*.

1. Положить N₀=Æ

2. Вычислить N₁= N₀ È {A | (A®a) Î P и a Î (N₀ È T)*}

3. Если N₁¹ N₀ , то положить N₀= N₁ и перейти к п.2; иначе положить N= N₁

4. Вычислить V_N’ = V_N Ç N, N_Б= V_N – V’_N, P’=P-P_Б , где P_Б ÍP – это множество правил, содержащих бесполезные нетерминалы X Î N_Б, т.е.

P_Б = {(X®a) Î P , (A®aXb) Î P для всех X ÎN_Б, где АÎ V’_N , a,b Î S*}

Пример: Рассмотренный алгоритм преобразует грамматику G=(V_N, T, P, S) = ({a, b, d}, {Q, A, B, C}, P, Q) c правилами:

Q ® ab

Q ® AC

A ® AB

B ® b

C ® db