Специальная математика. Соловьев А.Е. - 88 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Составители: 

Рубрика: 

├ <* A ∙ x ∙ y ∙*> x ∙ x ∙ *> ┤
├ <* B <* x =* x *> ┤
├ <* B =* C *> ┤
├ S ┤
Алгоритм распознавания:
1. Между символами строки вставляются отношения предшествования.
5. Строка просматривается слева направо до первого символа ∙*> , после этого просмотр
идет в обратном направлении до первого встречаемого символа *<∙ - между этими
символами и находится свертка, то есть правая часть правила, которая заменяется левой.
3. Восстанавливаются отношения предшествования.
4. Возвращение к первому пункту. Процесс продолжается до получения начального
нетерминального символа. Если этот процесс не завершиться успешно, строка не
принадлежит данной грамматике.
У этого метода есть минусы:
1. Далеко не во всех случаях удается построить грамматику с предшествованиями.
2. На практике символов может быть много сотен сотни и в результате получается
слабозаполненная матрица большой размерности.
7.16. Функции предшествования
Этот интересный метод придумал Р.Флойд – автор многих остроумных решений в
программировании. Вместо матрицы строятся две специальные функции f и g , такие что:
1. Если S
i
∙*> S
j
f(S
i
) > g(S
j
).
2. Если S
i
<* S
j
f(S
i
) < g(S
j
).
3. Если S
i
=* S
j
f(S
i
) = g(S
j
).
Тогда, вместо поиска с помощью матрицы отношения предшествования между символами,
просто происходит сравнение числовых значений соответствующих функций на больше
меньше равно.
Построение функций предшествования:
0. Строится матрица предшествования и начальные значения функций принимаются
равными единице: f(S
i
) = g(S
j
) = 1.
1. Матрица просматривается по строкам в поисках отношений ∙*> и, если
f(S
i
) > g(S
j
), то идем дальше, если же S
i
*> S
j
, а f(S
i
) ≤ g(S
j
), то увеличиваем значение f(S
i
)
- f(S
i
) = g(S
j
) + 1.
2. Матрица просматривается по столбцам в поисках отношений <*∙ и, если
f(S
i
) < g(S
j
), то идем дальше, если же S
i
<* S
j
, а f(S
i
) g(S
j
), то увеличиваем значение g(S
j
) -
g(S
j
) = f(S
i
) + 1.
3. Матрица просматривается в поисках отношений =* и, если f(S
i
) = g(S
j
), то идем дальше,
если S
i
=* S
j
, а f(S
i
) g(S
j
), то выравниваем значения функций путем увеличения
меньшего из значений до большего - f(S
i
) = g(S
j
) = max[f(S
i
), g(S
j
) ].
4. Возвращение к первому пункту.
Повторять до тех пор, пока рост функций не прекратится (или когда значение одной из
функций не превысит 2*n, где n - размерность матрицы - в этом случае алгоритм не
сходится).
Пример.
— 88 —
 ├ <* A ∙ x ∙ y ∙*> x ∙ x ∙ *> ┤
 ├ <* B <* x =* x *> ┤
 ├ <* B =* C *> ┤
 ├S┤

Алгоритм распознавания:
1. Между символами строки вставляются отношения предшествования.
5. Строка просматривается слева направо до первого символа ∙*> , после этого просмотр
    идет в обратном направлении до первого встречаемого символа *<∙ - между этими
    символами и находится свертка, то есть правая часть правила, которая заменяется левой.
3. Восстанавливаются отношения предшествования.
4. Возвращение к первому пункту. Процесс продолжается до получения начального
   нетерминального символа. Если этот процесс не завершиться успешно, строка не
   принадлежит данной грамматике.

У этого метода есть минусы:
1. Далеко не во всех случаях удается построить грамматику с предшествованиями.
2. На практике символов может быть много сотен сотни и в результате получается
   слабозаполненная матрица большой размерности.


                            7.16. Функции предшествования

           Этот интересный метод придумал Р.Флойд – автор многих остроумных решений в
    программировании. Вместо матрицы строятся две специальные функции f и g , такие что:
1. Если Si∙*> Sj  f(Si) > g(Sj).
2. Если Si <* Sj  f(Si) < g(Sj).
3. Если Si =* Sj  f(Si) = g(Sj).
Тогда, вместо поиска с помощью матрицы отношения предшествования между символами,
просто происходит сравнение числовых значений соответствующих функций на больше
меньше равно.

 Построение функций предшествования:
0. Строится матрица предшествования и начальные значения функций принимаются
равными единице: f(Si) = g(Sj) = 1.
1. Матрица просматривается по строкам в поисках отношений ∙*> и, если
    f(Si) > g(Sj), то идем дальше, если же Si *> Sj, а f(Si) ≤ g(Sj), то увеличиваем значение f(Si)
- f(Si) = g(Sj) + 1.
2. Матрица просматривается по столбцам в поисках отношений <*∙ и, если
   f(Si) < g(Sj), то идем дальше, если же Si <* Sj, а f(Si)  g(Sj), то увеличиваем значение g(Sj) -
g(Sj) = f(Si) + 1.
3. Матрица просматривается в поисках отношений =* и, если f(Si) = g(Sj), то идем дальше,
   если Si =* Sj, а f(Si)  g(Sj), то выравниваем значения функций путем увеличения
   меньшего из значений до большего - f(Si) = g(Sj) = max[f(Si), g(Sj) ].
4. Возвращение к первому пункту.
    Повторять до тех пор, пока рост функций не прекратится (или когда значение одной из
   функций не превысит 2*n, где n - размерность матрицы - в этом случае алгоритм не
   сходится).

Пример.


                                             — 88 —

Страницы