# PDA for parentheses language

Construct a PDA for the language described by the following CFG: $$S \to [S] \mid \{S\} \mid \Lambda$$

How can I develop a pushdown automaton for this language?

• In addition to showing how far you got on your own: what would be a simpler language accepted by a PDA, but not a finite one? (Oh, wait, there used to be curly braces) – greybeard May 4 '20 at 7:02

When you see [ or {, push it onto the stack.

When you see ], pop [ off the stack (if [ is not the top of stack, reject).

When you see }, pop { off the stack (if { is not the top of stack, reject).

Accept if at end of input, the stack is empty.

• What about that symbol which is present there what does that stand for??? – Rehan Redkar May 4 '20 at 7:36
• I have no idea what you're referring to. Note that your question would have been the same even with a single question mark. – Yuval Filmus May 4 '20 at 7:48
• That inverted V symbol which is seen in the production have any idea about that??? – Rehan Redkar May 4 '20 at 7:52
• It stands for the empty string. It feels like you should find better study materials. The empty string is a basic concept that would have been covered in class. We cannot stand for your course materials. – Yuval Filmus May 4 '20 at 7:54
• You cannot expect to answer questions such as constructing a PDF for a grammar, if you don't understand the syntax of grammars. – Yuval Filmus May 4 '20 at 7:55