Что такое контекстно-свободная грамматика для дополнения двойного слова над 0,1?
Каков CFG дополнения к L={ww|w принадлежит {0,1}*}?
2 ответа
Прежде всего обратите внимание на тот факт, что любое нечетное слово является частью языка. Давайте определим следующие языки:
L1 = {w1w | w {0,1} *}, L0 = {w0w | w {0,1} *}.
Эти языки могут быть определены с помощью следующего CFG:
Теперь посмотрим на L3:
Это контекст, свободный от закрытия до объединения и объединения.
Давайте докажем, что L3 - это язык, который мы ищем. Прежде всего, как мы видели, он имеет дело со всеми возможными словами нечетной длины. Что касается слов четной длины, если они есть в языке, существует, по крайней мере, одна пара терминалов, которая отличается с обеих сторон слова. Назовите эту пару а и б. Каждое четное слово можно разделить так:
и это точно
Это подразумевает, что языки 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.
Более четкое объяснение присутствует здесь .