Context Free Grammar Nested Brackets, Closing With A Possible ']'

1
votes

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.

Some examples of those strings accepted would be: (((], (()(] (()()) Some examples of those strings not accepted would be: (]), )(, ())

At current my grammar is as follows:

  • S -> epsilon
  • S -> ()
  • S -> (]
  • S -> (S)
  • S -> (S]
  • S -> (S
  • S -> SS

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?

Thanks in advance!

UPDATE:

I believe I have found the desired solution, though again I could be wrong. Starting with the base cases for the problem I have:

  • S->(]
  • S->(()]
  • S->()(]

From my inductive step

  • S->(I]
  • S->(I()]
  • S->((I)]
  • S->(()I]
  • S->(I)(]
  • S->()I(]

  • S->()(I]

  • I->()

  • I->II
  • I->(
  • I->(I)
1
compiler-constructioncontext-free-grammar
Your grammar also accepts ((]), which should be forbidden because the ] already closes all (. – sepp2k
CFGs allow multiple, distinct nonterminals. You may find that useful. – Sage Mitchell
@JakeMitchell could you explain and or provide a small example? – user3277807
@user3277807 He's saying you can use non-terminals other than S. Like S -> (X), X -> .... – sepp2k

1 Answers

2
votes

The second and third productions are redundant because of the first production (so the fourth and fifth productions will derive () and (], respectively).

However, your grammar will derive, for example, ((( (repeatedly using production 6 and then production 1), so it does not only recognize the desired language.