title: context-free matching of characters
body: <p>Given the three symbols: "(" ")" and ";"</p>
  
  <p>how can I create production rules of a context free grammar for S expressions, which meet the following criteria:</p>
  
  <ul>
  <li>The whole expression is nested in brackets, which means it starts
  with "(" and ends with ")".</li>
  </ul>
  
  <p>If the expression is read from left to right, then the amount of open brackets on any position of the expression (except for the last one) is greater than the amount of closed brackets. At the end of the expression the amount of open brackets should be equal to the closed brackets.</p>
  
  <ul>
  <li>Brackets can be nested in any way.</li>
  <li>Closing brackets must be separated from opening brackets with ";".</li>
  <li>The most inner brackets can contain a ";" OR remain empty.</li>
  <li>";" must not occur consecutively.</li>
  </ul>
  
  <p>Also upper case letters need to be used for any introduced Non-terminal letters.</p>
  
  <p>Strings contained in the grammar:</p>
  
  <pre><code>()
  (;)
  (((;)))
  ((;);((;)))
  (();(()))
  </code></pre>
  
  <p>Strings NOT contained in the grammar.</p>
  
  <pre><code>;
  (;;)
  (()())
  ());(()
  ();()
  ;()
  ε
  </code></pre>
  
  <p>I have tried using the following grammar, but I get some faulty values from it, any input/correction is appreciated.</p>
  
  <pre><code>S --&gt; (BAB)
  
  A --&gt; ; | ε | (A)
  
  B --&gt; B | A | A);(A
  </code></pre>