0

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.

2
Contributors
4
Replies
5
Views
6 Years
Discussion Span
Last Post by Saiiiira
0

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

The compute the same languages as Context Free Grammers.

0

>> 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.

0

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)

0

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)

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.