title: Context free grammar for non-palindrome
body: <p>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)</p>
  
  <pre><code>R -&gt; XRX | S
  S -&gt; aTb | bTa
  T -&gt; XTX | X | &lt;epsilon&gt;
  X -&gt; a | b
  </code></pre>
  
  <p>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 <code>S -&gt; aTb | bTa</code>, thus ensuring that a palindrome could never be generated.</p>
  
  <p>I will write down the semantics of the first two productions as I have understood it,</p>
  
  <ul>
  <li><code>S</code> generates strings which cannot be palindromes because their 1st and last alphabets are not equal</li>
  <li><code>R</code> consists of at-least one <code>S</code> as a sub-string ensuring that it is never a palindrome.</li>
  </ul>
  
  <p>I don't completely understand the semantics of the third production, i.e. .</p>
  
  <pre><code>   T -&gt; XTX | X | &lt;epsilon&gt;
     X -&gt; a | b
  </code></pre>
  
  <p>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 </p>
  
  <pre><code>T -&gt; XT | &lt;epsilon&gt;
  X -&gt; a | b
  </code></pre>
  
  <p>Aren't the two equivalent? As the later is more intuitive, why isn't it used?</p>