Тема 16: Теорема uvwxy


Данная теорема так же называется леммой о разрастании (о накачке) для КС-языков и формализует явление "периодичности" в этих языках.

Дана КС-грамматика в нормальной форме Хомского. Деревья вывода для нормальной формы Хомского — бинарные деревья.

Было доказано что существует определенная связь между высотой h, бинарного дерева, и длинной границы дерева (все терминальные символы – с лева на право).

Теорема «uvwxy»: Пусть L это КС-язык, тогда найдётся константа n и любое слово z из L, с |z|≥n. Слово z можно представить как uvwxy. Также выполняются свойства:

1. |vx|≥1 или vx≠ε;

2. |vwx|≤n;

3. uviwxiy∈ L.

Доказательство:

Пусть будет L язык порождаемый грамматикой G. Грамматика G это КС-грамматика и находится в нормальной форме Хомского. Обозначим L(G)=L. VN={A1,... Ak}, k=card(VN), константа n=2k.

Слово z из L, |z|≥n=2k, тогда существует Sz, и можно построить бинарное дерево для данного вывода.

       Выбираем первое повторение узлов при прохождении самой длинной дороги дерева снизу вверх. Пусть будут n1 и n2 те узлы которые повторяются.

Тогда узел n1 генерирует поддерево, имеющее границу w.

n1 ⇒ Aw

n2 ⇒ AvAx=>vwx

SuAyuvAxy=>uvwxy