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?
Tell me more
×
Computer Science Stack Exchange is a question and answer site for
students, researchers and practitioners of computer science. It's 100% free, no registration required.
|
|
||||
|
|
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. |
|||
|
|
|
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". |
||||
|
|
