When converting a CFG to a PDA I know that you get three main states, Qstart, Qloop and Qaccept. But Qloops will need a various amount of states, and my question is how many? Is there a way to find out the "worst case scenario" of how many states there can potentially be? I don't mean for one particular CFG, but in general. I'm having difficulties trying to figure out how I can calculate this...
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ I guess you mean to say : "how many states can potentially be necessary?", as you can always add more. You should correct your question. By the way, the answer was already available, though with a more direct title. $\endgroup$– babouCommented Mar 24, 2014 at 10:59
-
$\begingroup$ Possible duplicate (thanks, @babou) $\endgroup$– RaphaelCommented Mar 24, 2014 at 12:20
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
I do not know about Qstart, Qloop and Qaccept ... there are many ways to organize the construction of PDAs.
the minimal number of states required depends a bit on the formal model you use for defining PDAs. But essentially you need only one state (which means no finite control) if you allow pushing and popping several symbols in one transition.
Instead of having several states, you push a on the stack a symbol representing the state, and you pop it for the next transition. The top of the stack is as good a place as any to keep the state information.
If having to pop several symbols makes you unhappy, you can always use a pairs of symbols as a unique symbol. Cross-products are handy.
This of course implies that acceptance is by empty stack rather than final state, which can cause some problems related to the prefix property of some languages. If that becomes a problem, use a PDA with two states, one being used as accepting state.
PS This question is already answered in How to get 2-state PDA for CFG?
$\begingroup$
$\endgroup$
When converting CFG to NPDA ,then to simplify the process, first convert the CFG to Greibach Normal Form(GNF). Now using three states: Qstart, Qloop and Qaccept, you can generate all transition rules for the NPDA.
To start the process add the transition: $ δ(Qstart,λ,z)=\{(Qloop,Sz)\}$ where S start variable and z is stack start symbol.
And add the following transition to get the NPDA into a final state:$ δ(Qloop,λ,z)=\{(Qaccept,z)\}$.
Now using the production rules of the CFG you can easily generate all the other transitions which includes only $Qloop$. And here the number of transitions depend on the number of production rules.
answered Mar 24, 2014 at 10:01