patternMinor
CFG and PDA for the grammar that has perfectly nested parentheses and brackets
Viewed 0 times
perfectlytheparenthesescfgbracketspdahasnestedgrammarfor
Problem
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?
$\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?
Solution
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.
Context
StackExchange Computer Science Q#6719, answer score: 3
Revisions (0)
No revisions yet.