It is for me unclear how I can derive from a npda whether the lambda-transition means “I don’t care which symbol I read” or “I have read all the symbols”. For example, see the following automata: enter image description here

If I am correct, the red ones have the first meaning, and the green one the second.

Maybe I totally misunderstood lambda-transitions in npdas?

  • $\begingroup$ Can you specify what is the language that you are trying to recognize with the NPDA? $\endgroup$ Aug 26 at 19:40

1 Answer 1


Usually, the first symbol means what you expect to read from the input (1), the second what is the symbol at the top of the stack (2) and the third what will happen with the stack (3).

  1. $\lambda$ or $\varepsilon$ means the empty string, so this transition can be used without consuming any symbol from the input, i.e., it is a spontaneous transition over the input;
  2. $\lambda$ or $\varepsilon$ means "empty stack";
  3. $\lambda$ or $\varepsilon$ means pop from stack.

In your model, both red and green marked lambdas means spontaneous transition over the input, but they have a condition related to the top of the stack. In the first red, the stack must be empty. In the second the top of the stack must be X and in the green lambda the top of the stack must be + (if I'm reading that correctly).

Honestly, I have the impression that your modeling is incorrect. Can you present the language you are trying to recognize with this NPDA?

  • $\begingroup$ "expontaneous" isn't really an English word, although apparently it's used in some specialised sense in academic medicine. I've only ever seen it as a mistranslation of "espontáneo" (or "espontâneo"), which should be translated as "spontaneous". $\endgroup$
    – rici
    Aug 26 at 20:50
  • $\begingroup$ @rici thanks for you observation! My english is pretty rusty nowadays. $\endgroup$ Aug 29 at 17:32

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.