# GATE1994-1.16

1.7k views

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

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.

edited by
22
In option A, Regular grammars are already context-free grammars. Nothing to convert.
1
@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
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
Ans: C bcz pow(NPDA) is not equal to pow(PDA)

rest of them has equal power.

## Related questions

1
5.9k views
Which one of the following is FALSE? There is a unique minimal DFA for every regular language Every NFA can be converted to an equivalent PDA. Complement of every context-free language is recursive. Every nondeterministic PDA can be converted to an equivalent deterministic PDA.
The number of flip-flops required to construct a binary modulo $N$ counter is __________