# CFG and PDA for the grammar that has perfectly nested parentheses and brackets

I gotta make a CFG and PDA for the grammar that has perfectly nested parentheses and brackets.

\qquad\begin{align} S &\to [S] \\ S &\to (S) \\ S &\to SS \\ S &\to \varepsilon \end{align}

Not sure if this is correct, or how to make the PDA from it?

• Try using the standard construction from the proof that CFG and NPDA are equally powerful! Does "perfectly nested" exclude $([)]$ here? – Raphael Nov 19 '12 at 18:11

The language you study is a classic, the one-sided Dyck language (on two pairs of brackets). You can directly make a PDA by considering the following property of nested strings: every symbol closing bracket you read should match the last unmatched opening bracket. Keep the unmatched $[$ and $($ on the stack and you are ready to go.