title: Context Free Grammar Nested Brackets, Closing With A Possible ']'
body: <p>I am relatively new to CFG and am wondering if one of you might be able to help me determine if the current solution I have is correct. I was asked to generate the context free grammar which accepts the language of nested brackets such that if the last token is a right square bracket, it closes all remaining open left brackets.</p>
  
  <p>Some examples of those strings accepted would be: (((], (()(] (()())
  Some examples of those strings not accepted would be: (]), )(, ())</p>
  
  <p>At current my grammar is as follows:</p>
  
  <ul>
  <li>S -> epsilon </li>
  <li>S -> () </li>
  <li>S -> (] </li>
  <li>S -> (S) </li>
  <li>S -> (S] </li>
  <li>S -> (S </li>
  <li>S -> SS</li>
  </ul>
  
  <p>From all the examples I have tried, including those listed as both accepted and non accepted states above, I think that my CFG is correct. I'm wondering if there is any way to check this more concretely than simply randomly trying a large number of possibilities, and or if any of you can spot any errors?</p>
  
  <p>Thanks in advance!</p>
  
  <p>UPDATE:</p>
  
  <p>I believe I have found the desired solution, though again I could be wrong. Starting with the base cases for the problem I have: </p>
  
  <ul>
  <li>S->(]  </li>
  <li>S->(()]  </li>
  <li>S->()(]</li>
  </ul>
  
  <p>From my inductive step </p>
  
  <ul>
  <li>S->(I] </li>
  <li>S->(I()] </li>
  <li>S->((I)] </li>
  <li>S->(()I] </li>
  <li>S->(I)(] </li>
  <li>S->()I(] </li>
  <li><p>S->()(I]</p></li>
  <li><p>I->() </p></li>
  <li>I->II </li>
  <li>I->( </li>
  <li>I->(I)</li>
  </ul>