19 votes 19 votes Which of the following conversions is not possible (algorithmically)? Regular grammar to context free grammar Non-deterministic FSA to deterministic FSA Non-deterministic PDA to deterministic PDA Non-deterministic Turing machine to deterministic Turing machine Theory of Computation gate1994 theory-of-computation easy non-determinism + – Kathleen asked Oct 4, 2014 • recategorized Apr 25, 2021 by Lakshman Bhaiya Kathleen 7.6k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 30 votes 30 votes Correct Option: C Because if that would have been possible then NPDA and DPDA must had same powers, which is not the case. You can take example of NFA and DFA. Both are convertible to each other and hence share the same power. Gate Keeda answered Oct 7, 2014 • edited May 6, 2021 by soujanyareddy13 Gate Keeda comment Share Follow See all 2 Comments See all 2 2 Comments reply Sachin Mittal 1 commented Jan 23, 2017 reply Follow Share In option A, Regular grammars are already context-free grammars. Nothing to convert. 31 votes 31 votes Niraj Singh 2 commented Dec 7, 2017 reply Follow Share @sachin , but we can make a regular grammar to a non regular grammar but context free e.g S -> aB we can write it as S -> AB A->a and therefore we can say that " non regular grammar can generate a regular language" and it is true 1 votes 1 votes Please log in or register to add a comment.
7 votes 7 votes c is not possible because DPDA and NPDA are not of same powers so no algorthimic solution possible. except it all other options have a mechanical solutions Manu Thakur answered Oct 7, 2014 Manu Thakur comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes Ans: C bcz pow(NPDA) is not equal to pow(PDA) rest of them has equal power. rishu_darkshadow answered Oct 7, 2017 rishu_darkshadow comment Share Follow See all 0 reply Please log in or register to add a comment.
