search
Log In
12 votes
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

in Theory of Computation 1.7k views

3 Answers

22 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.


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
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
3 votes
Ans: C bcz pow(NPDA) is not equal to pow(PDA)

rest of them has equal power.
Answer:

Related questions

32 votes
7 answers
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.
asked Sep 22, 2014 in Theory of Computation Kathleen 5.9k views
22 votes
5 answers
2
3k views
The regular expression for the language recognized by the finite state automaton of figure is ______
asked Oct 4, 2014 in Theory of Computation Kathleen 3k views
14 votes
2 answers
3
2.9k views
Regarding the power of recognition of languages, which of the following statements is false? The non-deterministic finite-state automata are equivalent to deterministic finite-state automata. Non-deterministic Push-down automata are equivalent to deterministic ... equivalent to deterministic Turing machines. Multi-tape Turing machines are available are equivalent to Single-tape Turing machines.
asked Sep 26, 2014 in Theory of Computation Kathleen 2.9k views
16 votes
1 answer
4
2.4k views
The number of flip-flops required to construct a binary modulo $N$ counter is __________
asked Oct 4, 2014 in Digital Logic Kathleen 2.4k views
...