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?

  • $\begingroup$ 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) $\endgroup$ – 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.

  • $\begingroup$ What about that symbol which is present there what does that stand for??? $\endgroup$ – Rehan Redkar May 4 '20 at 7:36
  • $\begingroup$ I have no idea what you're referring to. Note that your question would have been the same even with a single question mark. $\endgroup$ – Yuval Filmus May 4 '20 at 7:48
  • $\begingroup$ That inverted V symbol which is seen in the production have any idea about that??? $\endgroup$ – Rehan Redkar May 4 '20 at 7:52
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 4 '20 at 7:54
  • $\begingroup$ You cannot expect to answer questions such as constructing a PDF for a grammar, if you don't understand the syntax of grammars. $\endgroup$ – Yuval Filmus May 4 '20 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.