177
правок
Изменения
→Аппроксимации самоприменимой грамматики
== Аппроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации: <tex>\mathrm {RTN }</tex> (recursive transition network) аппроксимацию и <tex>\mathrm {MN }</tex> (Mohri and Nederhof's) аппроксимацию — самоприменимой контекстно-свободной грамматики <tex> G = \langle N, \Sigma, P, S \rangle</tex> к регулярной грамматике. Для удобства будем считать, что грамматика представлена в [[Нормальная форма Хомского|НФХ]].
[[Файл:RTN_Automat.png|280px|thumb|right|Автоматы <tex>T_A,T_B</tex> для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
=== Сравнение двух методов ===
Ясно, что оба языка, генерируемых конечным автомат для первого метода и апрокисимируещей граматикой для второго метода, содержат в себе язык генерируемый исходной грамматикой.
Привлекателным свойством <tex>\mathrm {MN }</tex> аппроксимации по сравнению с <tex>\mathrm {RTN}</tex>, то, что она можеть быть применима к большим грамматикам: для каждого нетерминала грамматике <tex> G</tex>, добавляется не более одного нового нетерминала в <tex> G^*</tex> и размер результирующий грамматики максимум в <tex>2</tex> раза больше, чем размер исходной. Так как для <tex>\mathrm {RTN }</tex> апроксимации грамматики <tex> G = \langle N, \Sigma, P, S \rangle</tex>, количество состаяний апроксимируещего автомата в худшем случаи может составлять <tex> O(|N|^2)</tex>, что может быть критично для аппроксимации больших грамматик.
Также,еще несколько эффекивных методов аппрокимации можно найти в статьях, приведенных в ссылках.
