Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики — различия между версиями
Gaporf (обсуждение | вклад) м (→Псевдокод: tex) |
|||
(не показаны 33 промежуточные версии 5 участников) | |||
Строка 1: | Строка 1: | ||
− | Пусть дана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] | + | {{Задача |
+ | |definition = | ||
+ | Пусть дана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] <tex>\Gamma</tex> и слово <tex>w \in \Sigma^{*}</tex>. Требуется выяснить, выводится ли это слово в данной грамматике. | ||
+ | }} | ||
− | [[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ|Базовая версия]] данного алгоритма работает только для грамматик в [[нормальная форма Хомского|нормальной форме Хомского]]. Модифицируем алгоритм для работы на произвольных контекстно-свободных грамматиках. | + | [[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ|Базовая версия]] данного алгоритма работает только для грамматик в [[нормальная форма Хомского|нормальной форме Хомского]]. Модифицируем алгоритм для работы на произвольных контекстно-свободных грамматиках. Модификация алгоритма сильно проще в написании, чем приведение к [[нормальная форма Хомского|нормальной форме Хомского]], поэтому часто используют её, не смотря на то, что время работы у нее больше. |
== Алгоритм для произвольной грамматики == | == Алгоритм для произвольной грамматики == | ||
− | Будем решать задачу динамическим программированием. Введём динамику <tex>a\left[A,i,j\right] = \left[A \Rightarrow^{*} w[i | + | Будем решать задачу динамическим программированием. Введём динамику <tex>a\left[A,i,j\right] = \left[A \Rightarrow^{*} w[i \ldots j-1]\right] \ </tex>, аналогично [[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ|базовой версии]] алгоритма. |
− | Также введём вспомогательный четырехмерный массив <tex>h\left[A \rightarrow \alpha, i, j, k\right] = true</tex> тогда и только тогда, когда из префикса длины <tex>k</tex> правой части данного правила можно вывести <tex>w\left[i | + | Также введём вспомогательный четырехмерный массив <tex>h\left[A \rightarrow \alpha, i, j, k\right] = true \ </tex> тогда и только тогда, когда из префикса длины <tex>k</tex> правой части данного правила можно вывести <tex>w\left[i \ldots j-1\right]</tex>. |
− | Рассмотрим все тройки <tex>\lbrace \langle j, i \rangle | + | Рассмотрим все тройки <tex>\lbrace \langle j, i \rangle \mid j-i=m \rbrace</tex>, где <tex>m</tex> {{---}} константа и <tex>m < n</tex>, и <tex>k</tex> такое, что <tex>k < \left|\alpha\right|</tex>. |
* '''База динамики''': | * '''База динамики''': | ||
− | <tex>a\left[A, i, i+1\right] = true</tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow w[i]</tex>, иначе <tex>a\left[A, i, i+1\right] = false</tex>; | + | :<tex>a\left[A, i, i+1\right] = true \ </tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow w[i] \ </tex>, иначе <tex>a\left[A, i, i+1\right] = false \ </tex>; |
− | <tex>a\left[A, i, i\right] = true</tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow \varepsilon</tex>, иначе <tex>a\left[A, i, i\right] = false</tex>; | + | :<tex>a\left[A, i, i\right] = true \ </tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow \varepsilon \ </tex>, иначе <tex>a\left[A, i, i\right] = false \ </tex>; |
− | <tex> | + | :<tex>h\left[A \rightarrow \alpha, i, i, 0\right] = true \ </tex>. |
* '''Переход''': | * '''Переход''': | ||
− | Пусть значения для всех нетерминалов, пар <tex>\lbrace \langle j', i' \rangle | + | :Пусть значения для всех нетерминалов, пар <tex>\lbrace \langle j', i' \rangle \mid j' - i' < m \rbrace \ </tex> и <tex>\lbrace k' \mid k' < k \rbrace \ </tex> уже вычислены, поэтому вспомогательная динамика: <tex> h\left[A \rightarrow \alpha, i, j+1, k\right] = \bigvee\limits_{r=i \ldots j+1}\left(h\left[A \rightarrow \alpha, i, r, k-1\right] \wedge a\left[\alpha\left[k\right],r,j+1\right]\right)</tex> То есть, подстроку <tex>w[i \ldots j]</tex> можно вывести из префикса длины <tex>k</tex> правой части данного правила, если из префикса длины <tex>k-1</tex> правой части данного правила можно вывести <tex>w\left[i \ldots r-1\right]</tex>, а подстрока <tex>w[r \ldots j]</tex> выводится из <tex>k</tex>-го символа правой части правила. Это вычисление может обратится к <tex>a\left[A,i,j+1\right] </tex>, но на результат это не повлияет, так как в данный момент <tex>a\left[A,i,j+1\right]=false \ </tex>. |
− | + | :Но если <tex>\alpha\left[k\right]</tex> {{---}} терминал, то подстроку <tex>w[i \ldots j]</tex> можно вывести из префикса длины <tex>k</tex> правой части данного правила, если из префикса длины <tex>k-1</tex> правой части данного правила можно вывести <tex>w\left[i \ldots r-1\right] \ </tex>, а подстрока <tex>w[r \ldots j]</tex> выводится, если <tex>w\left[r \ldots j\right]=\alpha\left[k\right] \ </tex>. | |
+ | |||
+ | :Базовая динамика выражается так: <tex>a\left[A,i,j\right]=\bigvee\limits_{A \rightarrow \alpha}h\left[A \rightarrow \alpha, i, j, \left|\alpha\right|\right] \ </tex>. То есть, подстроку <tex>w[i \ldots j-1] \ </tex> можно вывести из нетерминала <tex>A</tex>, если из длины правой части данного правила можно вывести <tex>w\left[i \ldots j-1\right] </tex>. | ||
* '''Завершение''': | * '''Завершение''': | ||
− | После окончания работы ответ содержится в ячейке <tex>a\left[S, 1, n\right]</tex>, где <tex>n = |w|</tex>. | + | :После окончания работы ответ содержится в ячейке <tex>a\left[S, 1, n\right] </tex>, где <tex>n = |w|</tex>. |
+ | |||
+ | == Псевдокод == | ||
+ | <code> | ||
+ | '''CYK_Modified'''(S, Г): <font color = darkgreen>// S {{---}} строка длины n, Г {{---}} КС-грамматика </font color = darkgreen> | ||
+ | '''for''' i = 1..n | ||
+ | '''for''' Rj -> alpha <font color = darkgreen>// перебор состояний </font color = darkgreen> | ||
+ | '''if'''( A -> w[i] in Г) a[A, i, i+1] = true <font color = darkgreen>// если в грамматике Г присутствует правило A -> w[i] </font color = darkgreen> | ||
+ | '''else''' a[A, i, i+1] = false | ||
+ | '''if'''( A -> eps in Г) a[A, i, i] = true <font color = darkgreen>// если в грамматике Г присутствует правило A -> eps </font color = darkgreen> | ||
+ | '''else''' a[A, i, i] = false | ||
+ | h[A->alpha, i, i, 0] = true | ||
+ | '''for''' m = 1..n | ||
+ | '''for''' i = 1..n | ||
+ | j = i+m | ||
+ | '''for''' k = 1..M | ||
+ | '''for''' Rj -> alpha <font color = darkgreen>// перебор состояний </font color = darkgreen> | ||
+ | h[A->alpha, i, j+1, k] = OR( for r = i..j+1) (h[A->alpha, i, r, k-1] & a[alpha[k],r,j+1]) | ||
+ | '''for''' i = 1..n | ||
+ | '''for''' j = 1..n | ||
+ | '''for''' Rj -> alpha | ||
+ | a[A, i, j] = OR( for A->alpha) h[A->alpha, i, j, |alpha|] <font color = darkgreen>// где |alpha| {{---}} размер правой части правила</font color = darkgreen> | ||
+ | '''return''' a[S, 1, n] | ||
+ | |||
+ | </code> | ||
== Оценка сложности == | == Оценка сложности == | ||
Обозначим <tex>M = \max\limits_{A \rightarrow \alpha}\left|\alpha\right|</tex> — максимальную длину правой части правила. | Обозначим <tex>M = \max\limits_{A \rightarrow \alpha}\left|\alpha\right|</tex> — максимальную длину правой части правила. | ||
− | + | Обработки правил вида <tex>A \rightarrow w[i]</tex>, <tex>A \rightarrow \varepsilon</tex> и нахождение <tex>h\left[A \rightarrow \alpha, i, i, 0\right] \ </tex> выполняются за <tex>O(n \cdot |\Gamma|)</tex>. | |
+ | |||
+ | Время одного перехода вспомогательной динамики <tex>O(n)</tex>, суммарное число состояний <tex>O(n^2 \cdot |\Gamma| \cdot M)</tex>. Отсюда расчёт вспомогательной динамики занимает <tex>O \left( n^3 \cdot |\Gamma| \cdot M \right) \ </tex> времени, базовая динамика находится, как <tex>O \left( n^2 \cdot |\Gamma| \right)</tex>. Итоговая временная сложность алгоритма равна <tex>O \left( n^3 \cdot |\Gamma| \cdot M \right)</tex>. Алгоритму требуется <tex>O(n^2 \cdot |\Gamma| \cdot M) \ </tex> памяти. | ||
+ | |||
+ | == См. также == | ||
+ | * [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ|Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]] | ||
+ | * [[Алгоритм_Эрли|Алгоритм Эрли]] | ||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Контекстно-свободные грамматики]] | [[Категория: Контекстно-свободные грамматики]] | ||
+ | [[Категория:Динамическое программирование]] |
Версия 22:38, 23 мая 2019
Задача: |
Пусть дана контекстно-свободная грамматика и слово . Требуется выяснить, выводится ли это слово в данной грамматике. |
Базовая версия данного алгоритма работает только для грамматик в нормальной форме Хомского. Модифицируем алгоритм для работы на произвольных контекстно-свободных грамматиках. Модификация алгоритма сильно проще в написании, чем приведение к нормальной форме Хомского, поэтому часто используют её, не смотря на то, что время работы у нее больше.
Алгоритм для произвольной грамматики
Будем решать задачу динамическим программированием. Введём динамику базовой версии алгоритма.
, аналогичноТакже введём вспомогательный четырехмерный массив
тогда и только тогда, когда из префикса длины правой части данного правила можно вывести .Рассмотрим все тройки
, где — константа и , и такое, что .- База динамики:
- , если в грамматике присутствует правило , иначе ;
- , если в грамматике присутствует правило , иначе ;
- .
- Переход:
- Пусть значения для всех нетерминалов, пар и уже вычислены, поэтому вспомогательная динамика: То есть, подстроку можно вывести из префикса длины правой части данного правила, если из префикса длины правой части данного правила можно вывести , а подстрока выводится из -го символа правой части правила. Это вычисление может обратится к , но на результат это не повлияет, так как в данный момент .
- Но если — терминал, то подстроку можно вывести из префикса длины правой части данного правила, если из префикса длины правой части данного правила можно вывести , а подстрока выводится, если .
- Базовая динамика выражается так: . То есть, подстроку можно вывести из нетерминала , если из длины правой части данного правила можно вывести .
- Завершение:
- После окончания работы ответ содержится в ячейке , где .
Псевдокод
CYK_Modified(S, Г): // S — строка длины n, Г — КС-грамматика for i = 1..n for Rj -> alpha // перебор состояний if( A -> w[i] in Г) a[A, i, i+1] = true // если в грамматике Г присутствует правило A -> w[i] else a[A, i, i+1] = false if( A -> eps in Г) a[A, i, i] = true // если в грамматике Г присутствует правило A -> eps else a[A, i, i] = false h[A->alpha, i, i, 0] = true for m = 1..n for i = 1..n j = i+m for k = 1..M for Rj -> alpha // перебор состояний h[A->alpha, i, j+1, k] = OR( for r = i..j+1) (h[A->alpha, i, r, k-1] & a[alpha[k],r,j+1]) for i = 1..n for j = 1..n for Rj -> alpha a[A, i, j] = OR( for A->alpha) h[A->alpha, i, j, |alpha|] // где |alpha| — размер правой части правила return a[S, 1, n]
Оценка сложности
Обозначим
— максимальную длину правой части правила.Обработки правил вида
, и нахождение выполняются за .Время одного перехода вспомогательной динамики
, суммарное число состояний . Отсюда расчёт вспомогательной динамики занимает времени, базовая динамика находится, как . Итоговая временная сложность алгоритма равна . Алгоритму требуется памяти.