The formal language over the alphabet {'(',')'} consisting of words with an equal number of opening ('(') and closing (')') brackets, such that every prefix of the word has at least as many opening brackets as it has closing brackets.

That is, it contains exactly "expressions" consisting only of parentheses, which are "balanced" in the usual sense of the word.

The balanced braces language can be recognised by a context-free grammar (even by a deterministic pushdown automaton), but it is not a regular language -- usually the pumping lemma proof that the balanced braces language is not regular is given in introductory courses, but a better proof uses the Myhill theorem. Here's a context-free grammer for the language:

S → (S)S
S → ε
Here S is the start symbol (of course), and ε the null string.

Log in or register to write something here or to contact authors.