Материалы (4) (1115031)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов учебной работы