Looking at the above PDA, I am unsure whether or not it is normalized. Specifically, the loop transition from $q_1$ to $q_1$, because I know a transition must either push OR pop from the stack. Does this mean that there must be two separate transitions to push the * and then pop the *? Or is it normalized as is? Is it okay to have multiple transitions from a single state to another, some of which pop, and some of which push?

  • 2
    $\begingroup$ I encourage you to edit your question to include a self-contained definition of what you mean by "normalized". If you don't know what the definition is, you might want to ask whoever is using that term with you to define their terms. Thank you! $\endgroup$ – D.W. Mar 4 '17 at 0:01

What do you call a normalized PDA? There are many ways to specify that. Also, a PDA is defined by its transition fonction. The diagram is just a convenient graphical way to do that, as long as it is precise and easily read.

For the example you give, a transition is not represented by a directed edge, but by a directed edge together with a label. If you have an edge with two labels, as in your loop on $q_1$, that represents two transitions. Trying to do it with two separate loop edges would only make your diagram less readable.

Now, it is possible that your instructor has defined "normalized diagrams" in some way, and you should try to follow his wishes. But I do not remember of any such normalization of PDA diagrams with real technical importance.

Yes it is OK to have multiple transitions from one state to another. You could avoid it by introducing new intermediate states, but that would serve absolutely no purpose other than making your life miserable.

  • $\begingroup$ Thanks for the answer. In my textbook, and in class, part of the definition of a normalized PDA, was that a transition can only either push or pop a symbol. I've found normalized PDA definitions in academic papers (people.cs.aau.dk/~srba/files/NS:MFCS:07.pdf), but they really don't elaborate much further $\endgroup$ – tpm900 Mar 3 '17 at 23:40
  • $\begingroup$ Yes, requiring to have only a push or a pop of at most a single symbol is a common way of normalizing PDA transitions. But I could not be sure you meant that. Your diagram is fine and consistent with this requirement. Only recall that a transition is an edge together with a label. If an edge has two labels, that stand for 2 transitions. My difficulty in answering is due to the fact that you seemed to have a problem with the diagram representation, more than with the PDA itself. $\endgroup$ – babou Mar 4 '17 at 0:08

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.