Материалы (4) (Материалы к лекциям)

46Приведенные КС-грамматикиСимвол x  (VT  VN) называетсянедостижимым в грамматике G=(VT, VN, P, S), еслион не появляется ни в одной сентенциальной формеэтой грамматики.Символ А  VN называется бесплодным вграмматике G=(VT, VN, P, S), если множествовыводимых из этого символа терминальных цепочекпусто.КС-грамматика называется приведенной, если вней нет недостижимых и бесплодных символов.47Приведенные КС-грамматикиАлгоритм приведения грамматики:1.Найти и удалить все бесплодные символы иправила, их содержащие.2.Найти и удалить все недостижимые символы иправила, их содержащие.Примечание. Если начальный символ грамматики окажется бесплодным, тоследует удалить содержащие его правила, а сам символ оставить в алфавитенетерминалов VN, так как по определению грамматики VN обязан содержатьначальный символ.48Для нахождения бесплодных и недостижимыхсимволов полезен граф КС-грамматики: каждому символу из VT  VN соответствуетединственная вершина, помеченная этим символом;если в P есть правило с пустой правой частью , тограф имеет вершину, помеченную  ; вершина X соединяется с вершиной Y стрелкой(дугой), если в грамматике есть правило XY,,(VTVN)* ; X соединяется с вершиной , если в грамматикеесть правило X .49Алгоритм удаления бесплодных символов:1.

Отметить терминальные вершины (вершины,помеченные терминальными символами), а такжевершину , если таковая имеется.2. Если в Р есть правило А, где  состоит из ужеотмеченных в графе символов, а вершина А неотмечена, то отметить эту вершину. Повторятьшаг 2 пока возможно.3. Из грамматики удалить неотмеченные символы иправила, их содержащие.50Алгоритм удаления бесплодных символов:1. Отметить терминальные вершины (вершины, помеченныетерминальными символами), а также вершину , если такаяимеется.2.

Если в Р есть правило А, где  состоит из ужеотмеченных в графе символов, а вершина А не отмечена, тоотметить эту вершину. Повторять шаг 2 пока возможно.3. Из грамматики удалить неотмеченные символы и правила, ихсодержащие.Алгоритм удаления недостижимых символов:1. Отметить вершины, в которые есть путь из вершины S.2. Удалить из грамматики неотмеченные символы и правила, ихсодержащие.51Пример. Дана грамматикаG=({a, b, c, d, e}, {S, A, B, C, D}, P, S)P:S  aAB | CD  cDc | dC  aCDA  aA | a | cBbГраф грамматики G:SBaACDbde52Пример. Дана грамматикаG=({a, b, c, d, e}, {S, A, B, C, D}, P, S)P:S  aAB | CD  cDc | dC  aCDA  aA | a | cBbГраф грамматики G:SBaACDbdeНе отмеченные жирным кружком символы бесплодны.53Пример.

Дана грамматикаG=({a, b, c, d, e}, {S, A, B, C , D}, P, S)P:S  aAB | CD  cDc | dC  aCDA  aA | a | cBbГраф грамматики G:SBaACDbdeНе отмеченные жирным кружком символы бесплодны.Удалив из G бесплодные символы, получим эквивалентную грамматикуG1 =({a, b, c, d, e}, {S, A, B, D}, P1 , S)P1 : S  aABD  cDc | dA  aA | a | BbG1 не содержит бесплодных символов.Находим недостижимые символыГраф грамматики G1 :SBaAcDbde54G1 =({a, b, c, d, e}, {S, A, B, D}, P1 , S)P1 : S  aABD  cDc | dA  aA | a | BbГраф грамматики G1 :SBaAcDbdЗдесь неотмеченные символы являются недостижимыми.e55G1 =({a, b, c , d , e }, {S, A, B, D }, P1 , S)P1 : S  aABD  cDc | d лA  aA | a | BbГраф грамматики G1 :SBaAcDbdeЗдесь неотмеченные символы являются недостижимыми.Удалив из G1недостижимые символы, получимэквивалентнуюграмматику:G2 =({a, b}, {A, B}, P2 , S)P2 : S  aABG2 – приведенная грамматикаA  aA | a | BbL(G)=L(G1 )=L(G2 )={ an b | n1 }Задача.

Убедиться, что если в рассмотренном выше примере поменятьместами шаги (1) и (2) алгоритма приведения грамматики, то результатомбудет неприведенная грамматика.56Устранение правил с пустой правой частью из КС-грамматики1. Построить множество Х={AN | A}.2.

Удалить правила с пустой правой частью.3. Если SX, то S’ – новый начальный символ, S’S |  P.4.  AX правило вида B1A12A2...nAnn+1,где i((N – X)T)*nзаменить 2 правилами, соответствующими всем возможнымкомбинациям вхождений А между i:B12...nn+1B12...nAnn+1...B12A2...nAnn+1B1A12A2...nAnn+1Замечание: если все i=  i=1,...,n+1, то правило B невключать в новую грамматику.5. Удалить бесполезные символы и правила, их содержащие.57Пример.исходнаяграмматикаSBC | AbBCcAAa | эквивалентнаяграмматикаSC | b | AbCcAAa | a.