Изменения

{{Определение|definition='''[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная грамматика]]''' ('''КС-грамматика''', '''бесконтекстная грамматика''') — частный случай формальной грамматики, у которой левые части всех правил являются одиночными нетерминалами, то есть все её продукции имеют вид L → R, где L - нетерминалспособ описания формального языка, а R - последовательность терминалов и нетерминалов.задающийся:

Другими словами, для задания КС-грамматики необходимо задать: * Множество Множеством <tex>\Sigma</tex> терминальных символов* Множество Множеством <tex>N</tex> нетерминальных символов* Стартовый нетерминал Стартовым нетерминалом <tex>S \in N</tex>* Множество Множеством продукций вида <tex>A \rightarrow B_1 B_2 ... B_n</tex>, где <tex>A \in N</tex>, <tex>B_i \in \Sigma \cup N</tex>, то есть у которых левые части - одиночные нетерминалы, а правые - последовательности терминалов и нетерминалов.}}

funtion function CYK (a - строка длины n, G - набор правил вывода грамматики с m нетерминалами, S - стартовый нетерминал) -> bool