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

Question

Так что я нашел человека, с просьбой о контекстно-свободной грамматики для не палиндромов здесь: Context free grammar for non-palindrome

И данные CFGs были:

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

и

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

Мой вопрос: не будет ли это 'aaabba' не принят этим CFG, несмотря на то, что это не палиндром? ли это CFG быть более правильным, если это было правило, больше как:

T -> aTa | bTb | aTb | bTa | a | b | <epsilon> 

вместо последней строки, приведенные выше? Или я что-то не понимаю? : <

Answer 1

Первый в порядке, но второй нет.

Для первой, последовательность

R -> XRX -> aRa -> aSa -> aaTba -> aaXTXba -> aaaTbba -> aaabba. 

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