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...
Asked By : user2795095
Answered By : babou
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?
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/22992
0 comments:
Post a Comment
Let us know your responses and feedback