Working for my exam, this question popped up.

Given the production rules below, draw a pushdown automaton to recognise the language it generates:
S → AB
A → BA
B → BB
B → T
T → b

1. Since A has no empty transition, wouldn't this just end up in an infinite loop?
2. What order are the values entered into the stack.
If first you enter S, would it then be B at top of the stack and A at bottom or the other way around?
3. Below is my current interpretation of the PDA. Is it correct? Or does the question ask for the transition table?

PDA drawing


1 Answer 1


This grammar will in fact get into an infinite loop because there is no transition for A to turn into a terminal.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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