The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+9 votes

Which of the following conversions is not possible (algorithmically)?

  1. Regular grammar to context free grammar

  2. Non-deterministic FSA to deterministic FSA

  3. Non-deterministic PDA to deterministic PDA

  4. Non-deterministic Turing machine to deterministic Turing machine

asked in Theory of Computation by Veteran (52k points) | 830 views

3 Answers

+18 votes
Best answer

This will be 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.

answered by Boss (19.9k points)
edited by
In option A, Regular grammars are already context-free grammars. Nothing to convert.
@sachin , but we can make a regular grammar to a  non regular grammar but context free  


S -> aB

we can write it as

S -> AB


and therefore we can say that " non regular grammar can generate a regular language"

and it is true
+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
answered by Boss (42.3k points)
+3 votes
Ans: C bcz pow(NPDA) is not equal to pow(PDA)

rest of them has equal power.
answered by Loyal (6.9k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,548 questions
54,174 answers
71,129 users