Вопрос 7. Теорема о приведении КС-грамматики.
1. Достижимым, называется такой нетерминальный знак A?W, что существует вывод I ?G ? A ? , где ?, ? ? (V?W)*.
2. Производящим называется нетерминальный знак A?W, если существует вывод A?G ? , где ? ? V*.
Существенным, называется производящий и достижимый знак.
G2 — приведенная грамматика, если G2 — неукорачиваемая (т.е. не содержит пустой строки), и не содержит несущественных знаков.
Теорема 1.4. Для любой КС-грамматики существует эквивалентная ей приведенная КС-грамматика. Эквивалентность понимается с точностью до пустой строки.
1. В соответствии с Т. 1.3. применяем процедуру для получения неукорачивающей КС-грамматики.
2. Выделяем достижимые нетерминальные знаки и процедуру определения индуктивно.
2.1. Строим множество М1, куда включаем все знаки, достижимые из аксиом. М1?W , А?М1, если I ? ?A?.
2.i. Пусть определено множество Mi , содержащее достижимые знаки.
2.i+1. Строим множество Mi+1, как объединение множеств Mi с Mi| , где Mi| — множество нетерминальных знаков из правых частей продукции вида Ai ? ? , ? ? (V? W)+ (содержит нетерминальные знаки достижимые из продукции, в левой части которой стоят нетерминальные знаки принадлежащие множеству Mi )
2.k. Завершаем построение множества Mk (множества достижимых знаков), если по сравнению с предыдущим шагом это множество не изменилось ( Mk = Mk-1 ).
3. Выделяем производящие знаки.
3.1. Пусть задано Q1 ? W , для которого Ai ? Qi , Ai ? ? , ? ? V+ , знак Ai принадлежащие этому множеству является производящим.
3.i. Qi — множество производящих знаков.
3.i+1. Qi+1 = Qi ? Qi| , где Qi| — множество нетерминальных знаков, для которых из Ai выводится ? , где ?-строки из терминальных знаков ? ? (V?W)+ , п ринадлежащих Qi.
3.L. Завершаем построение, если Ql = Ql-1 .

Вопрос 8. Теорема о КС-грамматике без цепных правил.
Цепной называется продукция вида A?B, где A,B?W. Для каждой КС-грамматики имеющей цепные продукции имеется эквивалентная ей КС-грамматика без цепных продукций.
для всех нетерминальных знаков находим множество W с нижним индексом равным этому знаку такие что из А выводится В
строится множество p’’ следующим образом: если B?? не цепная продукция, то для всех B?WA p’’=p’’?(A??) (Просматриваем продукции грамматики и если находим не цепную продукцию B??, для которой B включено в полученное на 1 множество, то для каждого такого включения в множество p’’ добавляются продукции в левой части которых ставится знак А, а правая часть из текущей обозреваемой продукции)
получаем грамматику G=<V, W, p’’?p’, I>, где p’ – множество исходных продукций без цепных.