Лемма Огдена — различия между версиями
(Исправлена опечатка) |
Zernov (обсуждение | вклад) |
||
Строка 20: | Строка 20: | ||
Условие (1) выполнено, поскольку <tex>x</tex> содержит выделенную вершину, а именно <tex>v_p</tex>. Очевидно, что условие (4) выполнено в силу предложенного разбиения <tex>\omega</tex>. Кроме того, <tex>u</tex> содержит выделенную вершину, а именно потомка некоторого сына вершины <tex>u_1</tex>. Аналогично, выделенный потомок некоторого сына вершины <tex>a</tex> содержится в <tex>v</tex>. Таким образом, условие (2) выполнено. Поскольку между <tex>v_p</tex> и <tex>a</tex> не более <tex>2m + 3</tex> вершин, вершина <tex>a</tex> имеет не более <tex>n</tex> выделенных потомков, поэтому условие (3) выполнено. | Условие (1) выполнено, поскольку <tex>x</tex> содержит выделенную вершину, а именно <tex>v_p</tex>. Очевидно, что условие (4) выполнено в силу предложенного разбиения <tex>\omega</tex>. Кроме того, <tex>u</tex> содержит выделенную вершину, а именно потомка некоторого сына вершины <tex>u_1</tex>. Аналогично, выделенный потомок некоторого сына вершины <tex>a</tex> содержится в <tex>v</tex>. Таким образом, условие (2) выполнено. Поскольку между <tex>v_p</tex> и <tex>a</tex> не более <tex>2m + 3</tex> вершин, вершина <tex>a</tex> имеет не более <tex>n</tex> выделенных потомков, поэтому условие (3) выполнено. | ||
}} | }} | ||
+ | |||
+ | == См. также == | ||
+ | [[Лемма_о_разрастании_для_КС-грамматик|Лемма о разрастании для КС-грамматик]] | ||
+ | |||
+ | == Источники == | ||
+ | |||
+ | *Hopcroft, Motwani and Ullman {{---}} Automata Theory, Languages, and Computation {{---}} Addison-Wesley, 1979. ISBN 81-7808-347-7. | ||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Контекстно-свободные грамматики]] | [[Категория: Контекстно-свободные грамматики]] |
Версия 22:23, 3 января 2017
Лемма: |
Для каждой контекстно-свободной грамматики существует такое , что для любого слова длины не менее и для любых выделенных в не менее позиций, может быть представлено в виде , причем:
|
Доказательство: |
Введем следующие обозначения: и — длина самой длинной правой части правила из . Тогда в качестве возьмем . Рассмотрим дерево разбора для произвольного слова , у которого . В силу выбора в будет по крайне мере один путь от корня до листа длины не менее . Произвольным образом выделим в не менее позиций. Соответствующие этим позициям листья дерева будем называть выделенными.Пусть — корень , а — сын , который имеет среди своих потомков наибольшее число выделенных листьев (если таких несколько, то самый правый из них). Рассмотрим — путь от корня до листа.Будем называть ветвящейся ту вершину, у которой по крайне мере два сына имеют выделенных потомков. Докажем по индукции, что если среди Поскольку имеет хотя бы выделенных потомков, то содержит по крайне мере ветвящиеся вершин. Заметим, что — лист, поэтому . Будем называть левой ветвящейся вершиной, если ее сын, не принадлежащий пути , имеет выделенного потомка, лежащего слева от . В противном случае назовем правой ветвящейся вершиной. Рассмотрим последние вершины, принадлежащие пути . Предположим, что хотя бы вершины — левые ветвящиеся (случай, когда хотя бы вершины — правые ветвящиеся, разбирается аналогично). Пусть — последние левые ветвящиеся вершины. Поскольку , то среди них можно найти как минимум две вершины, соответствующие одному нетерминалу. Обозначим эти вершины и , причем — потомок . Тогда на рисунке показано, как представить в требуемом виде.
|
См. также
Лемма о разрастании для КС-грамматик
Источники
- Hopcroft, Motwani and Ullman — Automata Theory, Languages, and Computation — Addison-Wesley, 1979. ISBN 81-7808-347-7.