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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Try using the standard construction from the proof that CFG and NPDA are equally powerful! Does "perfectly nested" exclude $([)]$ here? $\endgroup$ – Raphael♦ Nov 19 '12 at 18:11
Add a comment
|
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
A: your CFG looks good.
B: There is a very well-known method of converting CFGs to PDAs.
Check https://www.youtube.com/watch?v=MJ9xNavURY8
Or the Wikipedia article on Pushdown automata
also this question has some interesting details.
But mainly - google "Converting CFG ro PDA".
