In this article, we have presented the Context free grammar (CFG) for properly nested parentheses or Balanced Parentheses / Expressions using all three set of brackets. This is an important topic in Theory of Computation (ToC).

Table of contents:

1. What is Balanced Parentheses?
2. CFG for Balanced Parentheses
3. Why this CFG works?
4. Example of using this CFG

Let us get started with Context free grammar (CFG) for Balanced Parentheses.

What is Balanced Parentheses?

Parentheses consist of opening and closing parentheses (,),{,},[,] and an expression has balanced parentheses if:

• Expression between a matching opening and closing parentheses is a balanced parentheses.
• There is no unmatched parentheses that is for every opening bracket, there is a closing bracket and vice versa.

Opening Parentheses are character ( or { or [.

Similarly, closing parentheses are ) or } or ] respectively.

This means ( and ) are pairs of opening and closing parentheses.

Examples of balanced parentheses:

• [()]
• {(([[[()]]]))}
• {}([])

Examples of unbalanced parentheses:

1. [)]
2. {(([[()]]]))}
3. [)(]

Note in example 1, there is no opening (.

In example 2, the are 2 opening [ but 3 closing ]. One opening [ is missing which makes in unbalanced.

In example 3, there is no opening round bracket ( before the closing round bracket ). This makes it unbalanced.

CFG for Balanced Parentheses

Let us assume in Balanced Parentheses, only round brackets are involved. In this case, the CFG for Balanced Parentheses are defined as follows:

CFG is G.

G = (V, Σ, R, S)

where:

• V is a set of variables
• Σ is a set of terminals
• R is a set of rules
• S is the starting variables and is a part of V.

We define the different attributes as:

• V = {S}
• Σ = {a, b}
• S = S
• R = { S -> e, S -> aSb, S -> SS }

Note e is null in this case.

Therefore, there are three rules:

1. S -> e
2. S -> aSb
3. S -> SS

Assume a is opening bracket ( and b is closing bracket ).

Substituting the values, we get the context free grammer as:

• V = {S}
• Σ = {(, )}
• S = S
• R = { S -> e, S -> (S), S -> SS }

Why this CFG works?

This context free grammer works because

S -> e

An empty expression is a balanced expression.

S -> (S)

Opening parenthesis followed by an expression followed by a closing parenthesis is a balanced expression provided the expression in between is a balanced expression which is true by assuming it to be S.

S -> SS

This is the case of a properly nested parentheses followed by properly nested parentheses.

This covers all cases of balanced parentheses so this Context Free Grammer G works.

In case, you want to involve all three braces that is (, { and [ along with the corresponding closing brace, then the context free grammer will be:

• V = {S}
• Σ = {(, ), {, }, [, ]}
• S = S

R will include:

1. S -> e
2. S -> (S)
3. S -> {S}
4. S -> [S]
5. S -> SS

Example of using this CFG

Let us assume we want to arrive at the balanced expression (())()() using our context free grammer G.

The steps are:

S ⇒ SS
⇒ (S)S
⇒ (S)SS
⇒ (SS)SS
⇒ ((S)S)SS
⇒ (()S)SS
⇒ (())SS
⇒ (())(S)S
⇒ (())()S
⇒ (())()(S)
⇒ (())()()

With this you have the complete idea of creating a Context Free grammer for properly nested parentheses or Balanced expression.