Get this book -> Problems on Array: For Interviews and Competitive Programming

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:

- What is Balanced Parentheses?
- CFG for Balanced Parentheses
- Why this CFG works?
- 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:

- [)]
- {(([[()]]]))}
- [)(]

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:

- S -> e
- S -> aSb
- 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:

- S -> e
- S -> (S)
- S -> {S}
- S -> [S]
- 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.