Что такое контекстно-свободная грамматика для дополнения двойного слова над 0,1?

Каков CFG дополнения к L={ww|w принадлежит {0,1}*}?

2 ответа

Решение

Прежде всего обратите внимание на тот факт, что любое нечетное слово является частью языка. Давайте определим следующие языки:

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^ м) (а)(x_2^ м)(y_1^ п) (б)(y_2^ п)


и это точно

(L1L2)U(L2L1)


Это подразумевает, что языки CFG не закрыты в дополнении.

Ранее предоставленный ответ неверен, так как он не охватывает все строки, присутствующие в дополнении к L, например, 011,110,11001 и т. Д. (Предыдущий ответ привел к потере некоторых ценных оценок, поэтому обновление :)) Вместо этого можно использовать следующую грамматику. докажите, что L-дополнение является CFL.

S→ A | B | AB | BA

A→ а | aAa | aAb | bAb | bAa

B→ b | aBa | aBb | bBb | bBa

A генерирует слова нечетной длины с a в центре. То же самое для B и b.

Более четкое объяснение присутствует здесь .

Другие вопросы по тегам