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.
Saiiiira 0 Newbie Poster
mrnutty 761 Senior Poster
>> I want to know more about these PDAs and the class of functions they compute.
The compute the same languages as Context Free Grammers.
Saiiiira 0 Newbie Poster
>> 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.
mrnutty 761 Senior Poster
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)
Saiiiira 0 Newbie Poster
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.