Контекстная грамматика для непалиндрома

Question

Мне нужен CFG, который будет генерировать строки, отличные от палиндромов. Решение предоставлено и выглядит следующим образом. (Введение в теорию вычислений - Sipser)

R -> XRX | S
S -> aTb | bTa
T -> XTX | X | <epsilon>
X -> a | b

Я получил общее представление о том, как работает эта грамматика. Он предписывает вставку подстроки, в каждой из которых есть соответствующие неравные алфавиты, путем производства S -> aTb | bTa, таким образом гарантируя, что палиндром никогда не будет сгенерирован.

Я запишу семантику первых двух произведений, как я ее понял,

• S генерирует строки, которые не могут быть палиндромами, потому что их первый и последний алфавиты не равны
• R состоит как минимум из одной S как подстроки, гарантирующей, что она никогда не будет палиндромом.

Я не совсем понимаю семантику третьего производства, т. Е.

   T -> XTX | X | <epsilon>
   X -> a | b

На мой взгляд, T может генерировать любую комбинацию a и b, т.е. {a, b} *. Почему это не могло быть как

T -> XT | <epsilon>
X -> a | b

Разве это не два эквивалента? Поскольку последний более интуитивно понятен, почему он не используется?

Answer 1

Определение T в этом грамматике действительно представляется ненужным усложнением.T может генерировать любую строку из a с и b с, так что более простое определение было бы столь же хорошим.

Я могу только догадываться, что произведения даны как они есть из-заколбасно-фабричный характер написания книги.

ОРИГИНАЛЬНЫЙ НЕПРАВИЛЬНЫЙ ОТВЕТ:

Они не эквивалентны, поскольку X сам по себе не может быть <epsilon>, а T не является комбинацией a и b.T может расширяться только до палиндрома (включая пустой палиндром, одиночный символ или палиндром с непарным центральным символом).

Если X может быть пустым, то T может расширяться дочто-нибудь, но не может.

ПРИМЕЧАНИЕ

Этот ответ основан на предположении, что намерение автора для производства T -> XTX состоит в том, что два идентичных не-терминалы в подстановке должны представлять одинаковые строки символов.Поскольку у меня нет текста для просмотра, я не знаю, является ли это предположение обоснованным, за исключением того, что оно мотивировано самим вопросом.Это предположение может быть ошибкой автора, если это не так в других местах.Я думаю, что в целом это требование не относится к контекстно-зависимым грамматикам.

Правильное производство будет:

R -> aRa | bRb | S
S -> aTb | bTa
T -> aTa | bTb | a | b | <epsilon>

Answer 2

Лучший способ убедиться, что у вас есть грамматика, которая генерирует только непалиндромы, заключается в следующем: Определить:

• Pal - язык палиндромов
• {a, b} * - язык, содержащий все строки в алфавите {a, б}
• Non-Pal - язык всех строк, которые не являются палиндромами (т.е. не в пал)

Наблюдатель, не являющийся приятелем = {a, b} * - приятель

Известно, что грамматика для Пала следующая:

• S -> лямбда | а | б | АСА | BSB

Грамматика для {a, b} * может быть записана следующим образом:

• S -> лямбда | Sa | Sb

Теперь, чтобы построить грамматику non-Pal, соблюдайте следующее:

• Если x является элементом не-Pal, то:
  • Axa является элементом non-Pal
  • bxb - это элемент не-Pal
• Если y является элементом {a, b} *, то:
  • айб это элемент не-пала
  • бя это элемент не-приятель

Объединяя всю эту информацию, грамматика для не-Пала была бы:

• S -> aSa | bSb | aAb | BAA
• A -> лямбда | Аа | Ab

Надеюсь, это прояснит ситуацию

Answer 3

Конструкция книги, которую я считаю, показывает некоторую симметрию для лучшего чтения.

Это означает, что она сначала строит что-нибудь, T. Затем есть обертка S, так что она больше не становится палиндромом S, изатем постройте все на нем.

Последнее может показаться интуитивным.Однако, если вы подумаете об определении или построении палиндрома, вы, возможно, поймете, почему письмо таким образом имеет смысл.

Если у вас есть палиндром, вы бы построили что-то вроде этого

T -> aTa |bTb |а |б |epsilon

И если мы хотим нарушить конструкцию, нам просто нужно убедиться, что один слой выглядит следующим образом (я использую T, чтобы быть одним слоем, а S - чем-то на один шаг после T)

S -> aTb

А другой слой нам вообще пофиг

S -> aTa |aTb |bTa |bTb

Так что образуется внутренний слой (T) и внешний слой (R), а также слой, нарушающий конструкцию палиндрома (S).Даже мысль T кажется избыточной, но она формирует аналогичную конструкцию, подобную R, выражая, таким образом, намерение построения.

Answer 4

Я нашел это определение непалиндрома довольно интуитивным.Я предполагаю, что автор начал с определения палиндрома

R -> aRa | bRb | a | b | <epsilon>

и теперь спросил, как это определение можно «испортить».

То есть он развернул определение три раза,обменял один aRa | bRb на aRb | bRa и обобщил оставшиеся произведения до (a|b)R(a|b).

Answer 5

Любой не палиндром можно разделить по середине, такой, что x (k)! = x (k + n)

n = половина длины x (i) = символ в i-й позиции

Имея это в виду, простое решение будет

R  -> aRa | bRb | T
T  -> aSb | bSa
S  -> aRa | bRb | a | b | T | episoln

Может генерировать все непалиндромы