The Gateway to Computer Science Excellence
+11 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

in Theory of Computation by Veteran (52.2k points) | 995 views

3 Answers

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

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

rest of them has equal power.
by Loyal (7.3k 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
50,737 questions
57,281 answers
104,842 users