Properly Nested Parentheses — Context-Free Languages

🌱 What Does “Properly Nested” Mean?

A string of parentheses is properly nested if:

1. Every opening ( has a matching closing ).
2. Closing parentheses never appear before a matching opening.
3. Parentheses are arranged in a neat, logical pattern — either:

• Side by side like: () () ()
• Nested inside like: ( ( ) )
• Or a mix of both: (()())

Here are examples:

✔ Proper: (), (()), (()()), ()()(), ((()()))
✘ Improper: )(, ((), ())(, ((())

---

🧱 Why Is This Language Context-Free?

Because the structure depends on what’s inside, not what’s around.

For example:

• If you see S, you can replace it with (S) — meaning you wrap the inside.
• Or with SS — meaning you place two valid structures next to each other.
• Or with ε — meaning it can also be empty.

This kind of “build from the inside out” definition is exactly what Context-Free Grammars are designed for.

---

🎯 A Simple CFG for Properly Nested Parentheses

A commonly used grammar is:

S → (S) | SS | ε

Let’s break this down in simple words:

• (S) → Add a pair of parentheses around a valid structure
• SS → Put two valid structures side by side
• ε → Allow the empty string, which is also balanced

These three rules allow us to build every properly nested parenthesis string.

---

💡 Building an Example Step-by-Step

Let’s say we want to generate the string:

(()())

Watch how the string grows from the start symbol:

S
→ (S)
→ (SS)
→ (S(S))
→ ((S)(S))
→ (()()( ))
→ (()())

---

🖼 Parse Tree Diagram (Easy to Read)

Here’s a simple tree showing how (()()) is formed:

                S
            _____|_____
           |          SS
           |       ___|___
           |      S       S
           |     / \     / \
           (    ( S )   ( S )
                 |       |
                 S       S
                 |       |
                 ε       ε

Each branch breaks the string into smaller balanced parts until we’re left with only ( and ).

---

🧠 Why This Matters in Theory of Computation

Properly nested parentheses are a classic example because:

✔ They cannot be recognized by regular languages

A simple finite automaton has no memory to “remember” how many ( are waiting to be closed.

✔ But they can be recognized by Pushdown Automata

A PDA uses a stack, which can push ( and pop when it sees ) — perfect for matching pairs.

✔ They demonstrate the power of CFGs

CFGs handle nested patterns beautifully and naturally.

---