title: Given a language, define its CFG
body: <p>Given </p>
  
  <pre><code>L1 = {w belongs to {a,b}* | has as many a as b}
  </code></pre>
  
  <p>Define a CFG G such that L(G)= L1</p>
  
  <p>In my opinion these productions should be the right answer</p>
  
  <pre><code>1) S → aSa
  
  2) S → bSb
  
  3) S → ε
  </code></pre>
  
  <p>My reasoning  was: </p>
  
  <p>L1 contains strings like { ab,aabb,aaabbb,...etc} </p>
  
  <p>Now I have a doubt: if I apply the above productions , in a nutshell:</p>
  
  <p><code>S → aSa</code><br>
  I apply the 1) so I get <code>S → aSa → aaSaa</code> the I choose 2) an I get <code>S → aSa → aaSaa → aabSbaa</code> and then using the empty string I get the final string  <code>S → aSa → aaSaa → aabSbaa → aabbaa</code></p>
  
  <p>Now, maybe I'm wrong but in the string <code>aabbaa</code>the number of a is not equal to the number of b</p>
  
  <p>Any help will be highly appreciated</p>
  
  <p>Joachim</p>