context-free-grammarcomputation-theory

Context free grammar for non-palindrome


I need a CFG which will generate strings other than palindromes. The solution has been provided and is as below.(Introduction to theory of computation - Sipser)

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

I get the general idea of how this grammar works. It mandates the insertion of a sub-string which has corresponding non-equal alphabets on its either half, through the production S -> aTb | bTa, thus ensuring that a palindrome could never be generated.

I will write down the semantics of the first two productions as I have understood it,

I don't completely understand the semantics of the third production, i.e. .

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

The way I see it, T can generate any combination of a and b, i.e. {a, b}*. Why could it not have been like

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

Aren't the two equivalent? As the later is more intuitive, why isn't it used?


Solution

  • The construction the book I believe is shows some symmetry for better reading.

    It means it first construct anything, T. Then there is a wrapper S, so that it becomes no longer a palindrome S, and then build everything upon it.

    The latter might seems to intuitive. However, if you think of the definition or construction of palindrome, you might understand why writing in such way make sense.

    If you have a palindrome, you would construct something like this

    T -> aTa | bTb | a | b | epsilon

    And if we want to violate construction, we just need to make sure that there is one layer looks like this (I use T to be one layer and S to something one step after T)

    S -> aTb

    And other layer we generally do not care

    S -> aTa | aTb | bTa | bTb

    So that forms the inner layer (T) and outer layer(R) and the layer that violates the construction of palindrome(S). Even thought T seems to be redundant, but it forms the similar construction like R, thus expressing the intention of the construction.