Domanda

From this section of the Wiki article on PDA, I've got a rough idea on the construction process of a PDA from a given CFG. What this article doesn't make clear is the step required when there are multiple production rules for a single non-terminal.

For example suppose we have a grammar given of the form :

Clearly, this grammar recognizes all string of the form x(ab)*y [coincidentally it's a regular language too].

Here I'm having problem constructing PDA from this grammar because of these 2 rules

That is, which of these 2 rules to be used in the Expansion phase, while pushing down to the stack?

È stato utile?

Soluzione

As given in this Slides your PDA will simulate leftmost derivations

Altri suggerimenti

For More Clear Details the slides have an example.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top