AlbaLed Posted October 31, 2003 Share Posted October 31, 2003 In the context of theory and prog. lang. why isn't Extended BNF more powerfull than "plain" BNF (extended bnf include: optional parts, the *, multiple choice options '|'). Explain your answer in terms of languages discussed in this forum in the field of theory. Enjoyyyyyyyyyyy!!!!!!!!! Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 1, 2003 Share Posted November 1, 2003 Originally posted by AlbaLed In the context of theory and prog. lang. why isn't Extended BNF more powerfull than "plain" BNF (extended bnf include: optional parts, the *, multiple choice options '|'). Explain your answer in terms of languages discussed in this forum in the field of theory. Enjoyyyyyyyyyyy!!!!!!!!! http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?Extended+BNF lists the following additional constructs in "Extended" BNF... [] Optional items. Well, A -> B[C]D can be represented with an extra production, A -> BCD | BD * Kleene closure. Well, A -> A B* D can be represented with an extra variable, A -> ACD; C -> BC | epsilon + One or more. Well, A -> A B+ D can be represented with an extra variable, A -> ACD; C -> BC | B {} List of possibilities. Break it into multiple productions. A -> A {B,C,D} E converts to A -> ABE | ACE | ADE Here's one for you: Why is the class of three-stack NPDA's no more powerful than the class of two-stack NPDA's? Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 1, 2003 Author Share Posted November 1, 2003 That's a good one nonevent, I'll have not seen this before, but here is my guess. Neither 2 stack nor 3 stack npda-s can be more powerfull than a turing machines, now we know that with a 2 stack PDA (NPDA) we can stimulate a turing machine, now my guess about the 3 stack NPDA is that you can probably stimulate a non-deterministic TM. But keep in mind that non-deterministic TMs are as powerfull as deterministic TM-s. You were thinking that ndTM solve NP problems in poly time and TM-s solve the same problems in exponential time, that does not make ndTM more powerfull than TMs. That relationship would only hold if ndTMs would solve some problem that TMs did not, for example the "halting problem". Your answer for the BNF is correct. CFL is closed under Kleen *, union, (for * and +), while the other two extensions seem just to save some paper and ink, :p Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 1, 2003 Share Posted November 1, 2003 Originally posted by AlbaLed Neither 2 stack nor 3 stack npda-s can be more powerfull than a turing machines, now we know that with a 2 stack PDA (NPDA) we can stimulate a turing machine, now my guess about the 3 stack NPDA is that you can probably stimulate a non-deterministic TM. But keep in mind that non-deterministic TMs are as powerfull as deterministic TM-s. You were thinking that ndTM solve NP problems in poly time and TM-s solve the same problems in exponential time, that does not make ndTM more powerfull than TMs. That relationship would only hold if ndTMs would solve some problem that TMs did not, for example the "halting problem". I think that's basically correct. The power of 2-stack NPDAs equals the power of TMs. So how can a 3-stack be any more powerful? You definitely can simulate an NTM on a 3-stack NPDA, since you can simulate an NTM with a TM. For that matter, you can simulate an NTM with a 2-stack NPDA. Don't ask me for the algorithm. ;) Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.