I understand that a PDA is an automata with a stack (LIFO) but I still can't understand how to answer a very simple question like this one. I've read so many pages on it, searched all over Google, watched countless videos on YouTube & yet I still can't grasp this for the life of me. This is my last resort.

I know if I understand this problem, I'll be able to the others.

Thanks for taking the time to read.

Let L be the language accepted by the pushdown automaton: 
M = (Q, ∑, gamma, delta, q, F) 
Q = {q,s}; 
∑ = {a,b}; 
gamma = {B};
F = {s}; 
and the transition function delta is defined as follows:


Write a regular expression that defines L.
  • 2
    $\begingroup$ To answer this question, you need to understand how pushdown automata work, so you can figure out what $L$ actually is. Then, you need to understand regular expressions so you can figure out a regular expression for $L$. There are many resources (your course materials, textbooks, web pages) that explain these things and it really isn't a productive use of anybody's time to write out a textbook chapter on PDAs and another on regular expressions to answer your question. Try to figure out what specifically you don't understand about the material you've read, and ask a question about that. $\endgroup$ – David Richerby Apr 9 '17 at 13:32
  • $\begingroup$ @DavidRicherby I should've mentioned that I understand regular expressions very well. It's the pushdown automata that I'm not understanding. But thanks for your input. $\endgroup$ – yabva89 Apr 9 '17 at 13:34
  • 2
    $\begingroup$ OK, so you're only asking people to write one chapter of a textbook for you! That's still too much, especially when the only thing you've told us is that you read stuff and didn't understand it, which gives no guidance at all about what you need help with. At the very least, you need to edit your question to make it clear that it's the PDA part that you need help with but that still isn't specific enough. $\endgroup$ – David Richerby Apr 9 '17 at 13:43
  • 1
    $\begingroup$ I have no idea what $[q,a,\lambda,s,B]$ means. Can you explain this notation? Is it "in state $q$, when reading $a$, if the top-of-stack is $\lambda$ (i.e. the stack is empty) move to state $s$ and push $B$"? Also, there are several acceptance conditions. Which one do you use? (Presumably by accepting state.) $\endgroup$ – Yuval Filmus Apr 9 '17 at 14:00
  • $\begingroup$ Your language seems to be $a^+b$. I'll let you figure out why. $\endgroup$ – Yuval Filmus Apr 9 '17 at 14:02

Your Answer

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

Browse other questions tagged or ask your own question.