3622
правки
Изменения
м
{| clear<div style="clear:both;" |}></div>
{| clear="both" |}
{| clear<div style="clear:both;" |}></div>
{| clear<div style="clear:both;" |}></div>
{| clear<div style="clear:both;" |}></div>
{| clear<div style="clear:both;" |}></div>
{| clear<div style="clear:both;" |}></div>
→Источники информации
* <tex>P</tex> {{---}} набор правил вывода (англ. ''production rules'' или ''productions'') вида <tex>A \rightarrow B_1 B_2 ... B_n</tex>, где <tex>A \in N</tex>, <tex>B_i \in \Sigma \cup N</tex>, то есть у которых левые части {{---}} одиночные нетерминалы, а правые - последовательности терминалов и нетерминалов.
}}
=== Пример ===
== Нормальная форма Хомского ==
'''[[Нормальная форма Хомского]]''' {{- --}} нормальная форма КС-грамматик, в которой все продукции имеют вид:* <tex>A → \rightarrow a</tex>, где ''<tex>A'' </tex> {{--- }} нетерминал, а ''<tex>a'' </tex> {{--- }} терминал* <tex>A → \rightarrow BC</tex>, где ''<tex>A''</tex>, ''<tex>B''</tex>, ''<tex>C'' </tex> {{-- -}} нетерминалы, причем ''<tex>B'' </tex> и ''<tex>C'' </tex> не являются начальными нетерминалами* <tex>S → ε\rightarrow \varepsilon</tex>, где <tex>S </tex> {{--- }} начальный нетерминал и ε <tex>\varepsilon</tex> {{--- }} пустая строка (данная продукция необходима, если в языке присуствует пустая строка)
[[Нормальная форма Хомского|Можно показать]], что любую КС-грамматику можно привести к нормальной форме Хомского, поэтому алгоритм является в этом плане универсальным.
== Алгоритм ==
'''Алгоритм Кока-Янгера-Касами''' (англ. ''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 \dots j]</tex>.
<tex>\begin{array}{l l}
A \rightarrow \varepsilon\ |\ BB\ |\ CD\\ B \rightarrow BB\ |\ CD\\
C \rightarrow (\\
D \rightarrow BE\ |\ )\\
E \rightarrow )\\
\end{array}</tex>
Инициализация массива <tex>d</tex>.
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|A
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|B
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|C
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
| align="center"| ●
|
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|D
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left; "
! colspan="7" style="background:#ffdead;"|E
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
Заполнение массива <tex>d</tex>.
Итерация <tex>m = 1</tex>.
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|A
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|B
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|C
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
| align="center"| ●
|
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|D
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left; "
! colspan="7" style="background:#ffdead;"|E
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
Итерация <tex>m = 2</tex>.
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|A
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|B
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|C
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
| align="center"| ●
|
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|D
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
| align="center"| ●
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left; "
! colspan="7" style="background:#ffdead;"|E
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
Итерация <tex>m = 3</tex>.
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|A
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
| align="center"| ●
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|B
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
| align="center"| ●
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|C
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
| align="center"| ●
|
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|D
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
| align="center"| ●
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left; "
! colspan="7" style="background:#ffdead;"|E
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
Итерация <tex>m = 4</tex>.
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|A
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
| align="center"| ●
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|B
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
| align="center"| ●
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|C
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
| align="center"| ●
|
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|D
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
| align="center"| ●
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left; "
! colspan="7" style="background:#ffdead;"|E
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
Итерация <tex>m = 5</tex>.
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|A
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
| align="center"| ●
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
| align="center"| ●
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|B
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
| align="center"| ●
| align="center"| ●
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
| align="center"| ●
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|C
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
| align="center"| ●
|
|
|-
! style="background:#efefef;"|2
|
|
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
|
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|D
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
| align="center"| ●
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left; "
! colspan="7" style="background:#ffdead;"|E
|-
! style="background:#efefef;"|! style="background:#efefef;"|1! style="background:#efefef;"|2! style="background:#efefef;"|3! style="background:#efefef;"|4! style="background:#efefef;"|5! style="background:#efefef;"|6
|-
! style="background:#efefef;"|1
|
|
|
|-
! style="background:#efefef;"|2
|
| align="center"| ●
|
|-
! style="background:#efefef;"|3
|
|
|
|-
! style="background:#efefef;"|4
|
|
|
|-
! style="background:#efefef;"|5
|
|
|
|-
! style="background:#efefef;"|6
|
|
| align="center"| ●
|}
== См. также ==
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Алгоритмы разбора]]
