I define a Decider PDA, a PDA (nondeterministic or deterministic) that does not loop for any input(I mean that it halt for every input,accept or reject). I want to know more about these PDAs and the class of functions they compute. Actually I didn't find about it in texts... I think that maybe non-loop is another word for it... Thanks.

Recommended Answers

All 4 Replies

>> I want to know more about these PDAs and the class of functions they compute.

The compute the same languages as Context Free Grammers.

>> I want to know more about these PDAs and the class of functions they compute.

The compute the same languages as Context Free Grammers.

I don't think so,because my lecturer told that in the case of determinism acceptors and decider are the same,but in the case of nondeterminism they are not....could you tell me somewhere to read about it?
Thanks.

This link talks about NPDA. In particular it states the following :

Theorem. A language is context-free iff some NPDA accepts it

That means, any language accepted by CFG can also be accepted by NPDA and any language accepted by NPDA can be accepted by CFG. Hence L(CFG) = L(NPDA)

This link talks about NPDA. In particular it states the following :


That means, any language accepted by CFG can also be accepted by NPDA and any language accepted by NPDA can be accepted by CFG. Hence L(CFG) = L(NPDA)

Yes,you are right,but I'm talking about the Deciders,what you say is right for Acceptors(the formal definition of PDA,it may loop forever for some input)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.