Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32



страница14/22
Дата07.11.2012
Размер1.2 Mb.
ТипКонспект
1   ...   10   11   12   13   14   15   16   17   ...   22

9.3. Устранение -правил


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

Алгоритм преобразования грамматики.


Пусть дана грамматика G=< VN, VT, S, R>, строится эквивалентная грамматика G’ =< VN’, VT, S, R’>.

  1. Построение множества N = { A / A + } – множества нетерминальных символов, из которых возможен вывод пустой цепочки. Множество N строится итерационно.

    1. На первом шаге строится N0:

N0 = { B / B    R}

    1. Последовательно строятся множества

Ni+1 = Ni { B / B R & ( Ni)* }.

    1. Построение продолжается до тех пор, пока не получим Ni+1 = = Ni, тогда N = Ni.

  1. Построение R — множества правил эквивалентной грамматики:

    1. если A0 B1 1 B2 ... Bk k R , k 0 и Bi N для 0 i k, но ни один символ в цепочках j, 1 j k не содержит символа из N, то включить в R все правила вида A 0 X1 1 X2 ...
      Xkk, где Xi — либо Bi, либо (при этом правило A не включать; это соответствует случаю, когда все i = );

    2. если S  N, включить в Rтакже правило S S, где S’ – новый начальный символ.

Таким образом, любая КС-грамматика может быть приведена к виду, когда R либо не содержит -правил, либо есть точно одно правило S и S не встречается в правых частях остальных правил из R.

Например, пусть дана грамматика G16 с множеством правил

SA B BC;

A aAb  ;

B dBc ;

C CCAc . Строим N0= {A, C}, N1= {A, C}= N. Поскольку L(G) (т.к. S N), правила грамматики примут вид
SA B B BC;

A aAb ab;

B dBc;

C CCAc c .
1   ...   10   11   12   13   14   15   16   17   ...   22

Похожие:

Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconМетодические указания к практическим занятиям Рязань 2004 удк 519. 713 (075)
Теория автоматов в задачах. Ч1: Методические указания к практическим занятиям/ Рязан гос радиотехн акад. Сост.: Н. И. Иопа. Рязань,...
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconУчебное пособие для студентов всех специальностей Москва 2003 ббк 22. 17я7 удк 519. 22 (075. 8) 6Н1 к 60
Калинина В. Н., Соловьев В. И. Введение в многомерный статистический анализ: Учебное пособие / гуу. – М., 2003. – 92 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций москва 2003 ббк вкб / 075 : 378 я 14
История экономики России XX века (1900 – 1917 гг.) : Конспект лекций. – М.: Мгту "Станкин", 2003. – 45 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций санкт-петербург 2009 удк 532. 6(075. 8) Ббк в334я73 а 65 Рецензент И. П. Арешев
Охватывает ток (рис. 16), то
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций м осква 2000 ббк ВКП / 075 : 378 я 14
История экономики России XIX века: Конспект лекций. М.: Мгту "Станкин", 2000. 68 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций по философии Часть 1 Античная философия Новосибирск 2007 удк 101. 8 (075) ббк ю3я73-1
Савостьянов А. Н. Конспект лекций по философии / Новосиб гос ун-т. Новосибирск, 2007. Ч. Античная философия. 68 с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconУчебное пособие для студентов всех специальностей Саратов 2009 удк 519. 17 Ббк 22. 174 С 32 Рецензенты
С32 Ведение в теорию графов: учеб пособие. Саратов: Сарат гос техн ун-т, 2009. 36с
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКонспект лекций Таганрог 2001 удк 621. 382. 019. 3 (075. 8) Механцев Е. Б
Обеспечение надежности электронных средств: конспект лекций. Таганрог: Изд-во трту, 2001
Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconКурс лекций Для студентов вузов Кемерово 2006 удк 113/119(075) ббк 87я7 М42 Рецензенты

Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7 С32 iconУчебное пособие Москва 2006 удк 341. 645: 347. 922(075) ббк 67. 412. 2 О 23

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org