Прежде всего обратите внимание на тот факт, что любое нечетное слово является частью языка.Давайте определим следующие языки:
L1 = {w1w | w {0,1} *}, L0 = {w0w | w {0,1} *}.
Эти языки могут быть определены с помощью следующего CFG:
S0 / 1 -> | 0S0 | 1S1 | 0S1 | 1S0
Теперь рассмотрим L3:
L3 = (L1) U (L2) U (L1L2) U (L2L1)
Не зависит от замыкания для объединения и объединения.
Давайте докажем, что L3 - это язык, который мы ищем.Прежде всего, как мы видели, он имеет дело со всеми возможными словами нечетной длины.Что касается слов четной длины, если они есть в языке, есть, по крайней мере, одна пара терминалов, которая отличается с обеих сторон слова.Назовите эту пару а и б.Каждое четное слово можно разделить следующим образом:
(x_1 ^ m) (a) (x_2 ^ m) (y_1 ^ n) (b) (y_2 ^ n)
, и этов точности
(L1L2) U (L2L1)
Это означает, что языки CFG не закрыты при дополнении.