Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ — различия между версиями
Kabanov (обсуждение | вклад) (→Пример работы) |
м (rollbackEdits.php mass rollback) |
||
(не показано 12 промежуточных версий 4 участников) | |||
Строка 12: | Строка 12: | ||
* <tex>N</tex> {{---}} множество, элементы которого называют '''нетерминалами''' (англ. ''nonterminals'') | * <tex>N</tex> {{---}} множество, элементы которого называют '''нетерминалами''' (англ. ''nonterminals'') | ||
* <tex>S</tex> {{---}} начальный символ грамматики (англ. ''start symbol'') | * <tex>S</tex> {{---}} начальный символ грамматики (англ. ''start symbol'') | ||
− | * <tex>P</tex> {{---}} набор правил вывода (англ. ''production rules'' или ''productions'') вида <tex>A \rightarrow B_1 B_2 | + | * <tex>P</tex> {{---}} набор правил вывода (англ. ''production rules'' или ''productions'') вида <tex>A \rightarrow B_1 B_2 \ldots B_n</tex>, где <tex>A \in N</tex>, <tex>B_i \in \Sigma \cup N</tex>, то есть у которых левые части {{---}} одиночные нетерминалы, а правые {{---}} последовательности терминалов и нетерминалов. |
}} | }} | ||
− | |||
=== Пример === | === Пример === | ||
Строка 35: | Строка 34: | ||
== Нормальная форма Хомского == | == Нормальная форма Хомского == | ||
− | '''[[Нормальная форма Хомского]]''' - нормальная форма КС-грамматик, в которой все продукции имеют вид: | + | '''[[Нормальная форма Хомского]]''' {{---}} нормальная форма КС-грамматик, в которой все продукции имеют вид: |
− | * A | + | * <tex>A \rightarrow a</tex>, где <tex>A</tex> {{---}} нетерминал, а <tex>a</tex> {{---}} терминал |
− | * A | + | * <tex>A \rightarrow BC</tex>, где <tex>A</tex>, <tex>B</tex>, <tex>C</tex> {{---}} нетерминалы, причем <tex>B</tex> и <tex>C</tex> не являются начальными нетерминалами |
− | * S | + | * <tex>S \rightarrow \varepsilon</tex>, где <tex>S</tex> {{---}} начальный нетерминал и <tex>\varepsilon</tex> {{---}} пустая строка (данная продукция необходима, если в языке присуствует пустая строка) |
− | [[Нормальная форма Хомского|Можно показать]], что любую КС-грамматику можно привести к нормальной форме Хомского | + | [[Нормальная форма Хомского|Можно показать]], что любую КС-грамматику можно привести к нормальной форме Хомского. |
== Алгоритм == | == Алгоритм == | ||
− | '''Алгоритм Кока-Янгера-Касами''' (англ. ''Cocke-Younger-Kasami algorithm'', англ. ''CYK-алгоритм'') {{---}} | + | '''Алгоритм Кока-Янгера-Касами''' (англ. ''Cocke-Younger-Kasami algorithm'', англ. ''CYK-алгоритм'') {{---}} алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского. Любую КС-грамматику можно привести к НФХ, поэтому алгоритм является универсальным для любой КС-грамматики. |
− | Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Дана строка <tex>w</tex> размером <tex>n</tex>. Заведем для неё трехмерный массив <tex>d</tex> размером <tex>|N| \times n \times n</tex>, состоящий из логических значений, и <tex>d[A][i][j] = true</tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>w[i \ | + | |
+ | Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Дана строка <tex>w</tex> размером <tex>n</tex>. Заведем для неё трехмерный массив <tex>d</tex> размером <tex>|N| \times n \times n</tex>, состоящий из логических значений, и <tex>d[A][i][j] = true \ </tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>w[i \ldots j]</tex>. | ||
Рассмотрим все пары <tex>\lbrace \langle j, i \rangle | j-i=m \rbrace</tex>, где <tex>m</tex> {{---}} константа и <tex>m < n</tex>. | Рассмотрим все пары <tex>\lbrace \langle j, i \rangle | j-i=m \rbrace</tex>, где <tex>m</tex> {{---}} константа и <tex>m < n</tex>. | ||
− | * <tex>i = j</tex>. Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки <tex>w</tex>. В таком случае <tex>d[A][i][i] = true</tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow w[i]</tex>. Иначе <tex>d[A][i][i] = false</tex>. | + | * <tex>i = j</tex>. Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки <tex>w</tex>. В таком случае <tex>d[A][i][i] = true \ </tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow w[i]</tex>. Иначе <tex>d[A][i][i] = false</tex>. |
− | * <tex>i \ne j</tex>. Значения для всех нетерминалов и пар <tex>\lbrace \langle j', i' \rangle | j' - i' < m \rbrace</tex> уже вычислены, поэтому <tex>d[A][i][j] = \bigvee\limits_{A \rightarrow BC}\bigvee\limits_{k = i}^{j-1} d[B][i][k] \wedge d[C][k+1][j]</tex>. То есть, подстроку <tex>w[i \ | + | * <tex>i \ne j</tex>. Значения для всех нетерминалов и пар <tex>\lbrace \langle j', i' \rangle | j' - i' < m \rbrace</tex> уже вычислены, поэтому <tex>d[A][i][j] = \bigvee\limits_{A \rightarrow BC}\bigvee\limits_{k = i}^{j-1} d[B][i][k] \wedge d[C][k+1][j] \ \ </tex>. То есть, подстроку <tex>w[i \ldots j]</tex> можно вывести из нетерминала <tex>A</tex>, если существует продукция вида <tex>A \rightarrow BC</tex> и такое <tex>k</tex>, что подстрока <tex>w[i \ldots k]</tex> выводима из <tex>B</tex>, а подстрока <tex>w[k + 1 \ldots j]</tex> выводится из <tex>C</tex>. |
[[Файл:CYK_rule_2.jpg|400px]] | [[Файл:CYK_rule_2.jpg|400px]] | ||
Строка 58: | Строка 58: | ||
=== Количество способов вывести слово === | === Количество способов вывести слово === | ||
− | Если массив будет хранить целые числа, а формулу заменить на <tex>d[A][i][j] = \sum\limits_{A \rightarrow BC}\sum\limits_{k = i}^{j-1} d[B][i][k] \cdot d[C][k + 1][j]</tex>, то <tex>d[A][i][j]</tex> {{---}} количество способов получить подстроку <tex>w[i \ | + | Если массив будет хранить целые числа, а формулу заменить на <tex>d[A][i][j] = \sum\limits_{A \rightarrow BC}\sum\limits_{k = i}^{j-1} d[B][i][k] \cdot d[C][k + 1][j] \ \ </tex>, то <tex>d[A][i][j]</tex> {{---}} количество способов получить подстроку <tex>w[i \ldots j]</tex> из нетерминала <tex>A</tex>. |
=== Минимальная стоимость вывода слова === | === Минимальная стоимость вывода слова === | ||
− | Пусть <tex>H(A \rightarrow BC)</tex> {{---}} стоимость вывода по правилу <tex>A \rightarrow BC</tex>. Тогда, если использовать формулу <tex>d[A][i][j] = \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1} ( d[B][i][k] + d[C][k + 1][j] + H(A \rightarrow BC) )</tex>, то <tex>d[A][i][j]</tex> {{---}} минимальная стоимость вывода подстроки <tex>w[i \ | + | Пусть <tex>H(A \rightarrow BC)</tex> {{---}} стоимость вывода по правилу <tex>A \rightarrow BC</tex>. Тогда, если использовать формулу <tex>d[A][i][j] = \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1} ( d[B][i][k] + d[C][k + 1][j] + H(A \rightarrow BC) ) \ \ </tex>, то <tex>d[A][i][j]</tex> {{---}} минимальная стоимость вывода подстроки <tex>w[i \ldots j]</tex> из нетерминала <tex>A</tex>. |
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является частным случаем задачи динамического программирования на подотрезке. | Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является частным случаем задачи динамического программирования на подотрезке. | ||
Строка 76: | Строка 76: | ||
<tex>\begin{array}{l l} | <tex>\begin{array}{l l} | ||
− | A \rightarrow \varepsilon|BB|CD\\ | + | A \rightarrow \varepsilon\ |\ BB\ |\ CD\\ |
− | B \rightarrow BB|CD\\ | + | B \rightarrow BB\ |\ CD\\ |
C \rightarrow (\\ | C \rightarrow (\\ | ||
− | D \rightarrow BE|)\\ | + | D \rightarrow BE\ |\ )\\ |
E \rightarrow )\\ | E \rightarrow )\\ | ||
\end{array}</tex> | \end{array}</tex> | ||
− | Дано слово <tex>w = | + | Дано слово <tex>w = ()(())</tex>. |
− | |||
Инициализация массива <tex>d</tex>. | Инициализация массива <tex>d</tex>. | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|A | + | ! colspan="7" style="background:#ffdead;"|A |
|- | |- | ||
! | ! | ||
Строка 148: | Строка 147: | ||
| | | | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|B | + | ! colspan="7" style="background:#ffdead;"|B |
|- | |- | ||
! | ! | ||
Строка 207: | Строка 206: | ||
| | | | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|C | + | ! colspan="7" style="background:#ffdead;"|C |
|- | |- | ||
! | ! | ||
Строка 266: | Строка 265: | ||
| | | | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|D | + | ! colspan="7" style="background:#ffdead;"|D |
|- | |- | ||
! | ! | ||
Строка 325: | Строка 324: | ||
| align="center"| ● | | align="center"| ● | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; " | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|E | + | ! colspan="7" style="background:#ffdead;"|E |
|- | |- | ||
! | ! | ||
Строка 384: | Строка 383: | ||
| align="center"| ● | | align="center"| ● | ||
|} | |} | ||
− | + | <div style="clear:both;"></div> | |
− | |||
Заполнение массива <tex>d</tex>. | Заполнение массива <tex>d</tex>. | ||
− | |||
Итерация <tex>m = 1</tex>. | Итерация <tex>m = 1</tex>. | ||
− | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | |
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | ! colspan="7" style="background:#ffdead;"|A |
− | ! colspan="7"|A | ||
|- | |- | ||
! | ! | ||
Строка 453: | Строка 449: | ||
| | | | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|B | + | ! colspan="7" style="background:#ffdead;"|B |
|- | |- | ||
! | ! | ||
Строка 512: | Строка 508: | ||
| | | | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|C | + | ! colspan="7" style="background:#ffdead;"|C |
|- | |- | ||
! | ! | ||
Строка 571: | Строка 567: | ||
| | | | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|D | + | ! colspan="7" style="background:#ffdead;"|D |
|- | |- | ||
! | ! | ||
Строка 630: | Строка 626: | ||
| align="center"| ● | | align="center"| ● | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; " | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|E | + | ! colspan="7" style="background:#ffdead;"|E |
|- | |- | ||
! | ! | ||
Строка 689: | Строка 685: | ||
| align="center"| ● | | align="center"| ● | ||
|} | |} | ||
− | + | <div style="clear:both;"></div> | |
Итерация <tex>m = 2</tex>. | Итерация <tex>m = 2</tex>. | ||
− | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | |
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | ! colspan="7" style="background:#ffdead;"|A |
− | ! colspan="7"|A | ||
|- | |- | ||
! | ! | ||
Строка 753: | Строка 748: | ||
| | | | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|B | + | ! colspan="7" style="background:#ffdead;"|B |
|- | |- | ||
! | ! | ||
Строка 812: | Строка 807: | ||
| | | | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|C | + | ! colspan="7" style="background:#ffdead;"|C |
|- | |- | ||
! | ! | ||
Строка 871: | Строка 866: | ||
| | | | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|D | + | ! colspan="7" style="background:#ffdead;"|D |
|- | |- | ||
! | ! | ||
Строка 930: | Строка 925: | ||
| align="center"| ● | | align="center"| ● | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; " | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|E | + | ! colspan="7" style="background:#ffdead;"|E |
|- | |- | ||
! | ! | ||
Строка 989: | Строка 984: | ||
| align="center"| ● | | align="center"| ● | ||
|} | |} | ||
− | + | <div style="clear:both;"></div> | |
Итерация <tex>m = 3</tex>. | Итерация <tex>m = 3</tex>. | ||
− | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | |
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | ! colspan="7" style="background:#ffdead;"|A |
− | ! colspan="7"|A | ||
|- | |- | ||
! | ! | ||
Строка 1053: | Строка 1047: | ||
| | | | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|B | + | ! colspan="7" style="background:#ffdead;"|B |
|- | |- | ||
! | ! | ||
Строка 1112: | Строка 1106: | ||
| | | | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|C | + | ! colspan="7" style="background:#ffdead;"|C |
|- | |- | ||
! | ! | ||
Строка 1171: | Строка 1165: | ||
| | | | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|D | + | ! colspan="7" style="background:#ffdead;"|D |
|- | |- | ||
! | ! | ||
Строка 1230: | Строка 1224: | ||
| align="center"| ● | | align="center"| ● | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; " | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|E | + | ! colspan="7" style="background:#ffdead;"|E |
|- | |- | ||
! | ! | ||
Строка 1289: | Строка 1283: | ||
| align="center"| ● | | align="center"| ● | ||
|} | |} | ||
− | + | <div style="clear:both;"></div> | |
Итерация <tex>m = 4</tex>. | Итерация <tex>m = 4</tex>. | ||
− | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | |
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | ! colspan="7" style="background:#ffdead;"|A |
− | ! colspan="7"|A | ||
|- | |- | ||
! | ! | ||
Строка 1353: | Строка 1346: | ||
| | | | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|B | + | ! colspan="7" style="background:#ffdead;"|B |
|- | |- | ||
! | ! | ||
Строка 1412: | Строка 1405: | ||
| | | | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|C | + | ! colspan="7" style="background:#ffdead;"|C |
|- | |- | ||
! | ! | ||
Строка 1471: | Строка 1464: | ||
| | | | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|D | + | ! colspan="7" style="background:#ffdead;"|D |
|- | |- | ||
! | ! | ||
Строка 1530: | Строка 1523: | ||
| align="center"| ● | | align="center"| ● | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; " | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|E | + | ! colspan="7" style="background:#ffdead;"|E |
|- | |- | ||
! | ! | ||
Строка 1589: | Строка 1582: | ||
| align="center"| ● | | align="center"| ● | ||
|} | |} | ||
− | + | <div style="clear:both;"></div> | |
Итерация <tex>m = 5</tex>. | Итерация <tex>m = 5</tex>. | ||
− | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | |
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | ! colspan="7" style="background:#ffdead;"|A |
− | ! colspan="7"|A | ||
|- | |- | ||
! | ! | ||
Строка 1653: | Строка 1645: | ||
| | | | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|B | + | ! colspan="7" style="background:#ffdead;"|B |
|- | |- | ||
! | ! | ||
Строка 1712: | Строка 1704: | ||
| | | | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|C | + | ! colspan="7" style="background:#ffdead;"|C |
|- | |- | ||
! | ! | ||
Строка 1771: | Строка 1763: | ||
| | | | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; float: left;" | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|D | + | ! colspan="7" style="background:#ffdead;"|D |
|- | |- | ||
! | ! | ||
Строка 1830: | Строка 1822: | ||
| align="center"| ● | | align="center"| ● | ||
|} | |} | ||
− | {| border="1" style="width: 150px; height: 150px; " | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|E | + | ! colspan="7" style="background:#ffdead;"|E |
|- | |- | ||
! | ! | ||
Строка 1889: | Строка 1881: | ||
| align="center"| ● | | align="center"| ● | ||
|} | |} | ||
− | + | <div style="clear:both;"></div> | |
== См. также == | == См. также == | ||
Строка 1903: | Строка 1895: | ||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Контекстно-свободные грамматики]] | [[Категория: Контекстно-свободные грамматики]] | ||
+ | [[Категория: Алгоритмы разбора]] |
Текущая версия на 19:17, 4 сентября 2022
Задача: |
Пусть дана контекстно-свободная грамматика в нормальной форме Хомского и слово . Требуется выяснить, выводится ли это слово в данной грамматике. |
Контекстно-свободная грамматика
Определение: |
Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — способ описания формального языка, представляющий собой четверку
, где:
|
Пример
Терминалы
.Нетерминалы
.Правила вывода
:
Данная грамматика задает язык правильных скобочных последовательностей. Например, последовательность может быть выведена следующим образом:
Нормальная форма Хомского
Нормальная форма Хомского — нормальная форма КС-грамматик, в которой все продукции имеют вид:
- , где — нетерминал, а — терминал
- , где , , — нетерминалы, причем и не являются начальными нетерминалами
- , где — начальный нетерминал и — пустая строка (данная продукция необходима, если в языке присуствует пустая строка)
Можно показать, что любую КС-грамматику можно привести к нормальной форме Хомского.
Алгоритм
Алгоритм Кока-Янгера-Касами (англ. Cocke-Younger-Kasami algorithm, англ. CYK-алгоритм) — алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского. Любую КС-грамматику можно привести к НФХ, поэтому алгоритм является универсальным для любой КС-грамматики.
Будем решать задачу динамическим программированием. Дана строка размером . Заведем для неё трехмерный массив размером , состоящий из логических значений, и тогда и только тогда, когда из нетерминала правилами грамматики можно вывести подстроку .
Рассмотрим все пары
, где — константа и .- . Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки . В таком случае , если в грамматике присутствует правило . Иначе .
- . Значения для всех нетерминалов и пар уже вычислены, поэтому . То есть, подстроку можно вывести из нетерминала , если существует продукция вида и такое , что подстрока выводима из , а подстрока выводится из .
После окончания работы значение
содержит ответ на вопрос, выводима ли данная строка в данной грамматике, где — начальный символ грамматики.Модификации
Количество способов вывести слово
Если массив будет хранить целые числа, а формулу заменить на
, то — количество способов получить подстроку из нетерминала .Минимальная стоимость вывода слова
Пусть
— стоимость вывода по правилу . Тогда, если использовать формулу , то — минимальная стоимость вывода подстроки из нетерминала .Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является частным случаем задачи динамического программирования на подотрезке.
Асимптотика
Обработка правил вида
выполняется за .Проход по всем подстрокам выполняется за
. В обработке одной подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за . В итоге получаем конечную сложность .Следовательно, общее время работы алгоритма — нетерминалов грамматики.
. Кроме того, алгоритму требуется память на массив объемом , где — количествоПример работы
Дана грамматика правильных скобочных последовательностей в нормальной форме Хомского.
Дано слово
.
Инициализация массива .
A | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ||||||
3 | ||||||
4 | ||||||
5 | ||||||
6 |
B | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ||||||
3 | ||||||
4 | ||||||
5 | ||||||
6 |
C | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
D | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
E | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
Заполнение массива
.
Итерация .
A | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ||||||
4 | ● | |||||
5 | ||||||
6 |
B | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ||||||
4 | ● | |||||
5 | ||||||
6 |
C | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
D | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
E | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
Итерация
.A | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ||||||
4 | ● | |||||
5 | ||||||
6 |
B | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ||||||
4 | ● | |||||
5 | ||||||
6 |
C | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
D | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ● | |||||
5 | ● | |||||
6 | ● |
E | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
Итерация
.A | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
B | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
C | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
D | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ● | |||||
5 | ● | |||||
6 | ● |
E | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
Итерация
.A | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
B | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
C | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
D | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ● | |||||
5 | ● | |||||
6 | ● |
E | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
Итерация
.A | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | ● | ||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
B | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | ● | ||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
C | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
D | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ● | |||||
5 | ● | |||||
6 | ● |
E | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |