MyQuestionIcon

1

You visited us 1 times! Enjoying our articles? Unlock Full Access!

In which of t...

Question

In which of the cases stated below is the following statement true?
"For every non-deterministic machine $M_{1}$ there exists and equivalent deterministic machine $M_{2}$ recognizing the same language".

A

M_{1}

is a non-deterministic Turning machine

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

B

M_{1}

is a non-deterministic PDA

No worries! We‘ve got your back. Try BYJU‘S free classes today!

C

For no machine

M_{1}

use the above statement true

No worries! We‘ve got your back. Try BYJU‘S free classes today!

D

M_{1}

is non-deteministic finite automation

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

Open in App

Solution

The correct option is D $M_{1}$ is non-deteministic finite automation
(a) There exist an algorithm to convert every NFA to DFA. So recognition power of NFA and DFA, is same.
(b) Since there exist no algorithm to convert NPDA to DPDA and recognition power of both are not same.
(c) The recognition power of NTM(non-deterministic Turing machine) and DTM (deterministic Turning machine) is same.
(d) Since for turing machines and finite automation the above statement is true so (d) is not true

Suggest Corrections

thumbs-up

0

Similar questions

Q. Which of the following statements is/are FALSE?
1. For every non-deterministic Turing machine,there exists an equivalent deterministic Turing machine
2. Turing recognizable languages are closed under union and complemenetation
3. Turing decidable languages are closed under intersection and complemenetation
4. Turing recognizable languages are closed under union and intersection

Q. Consider the following problems regarding decidability.
I. Given a Turing Machine M, whether L(M) is context free.
II. Given a Non-deterministic PDA P, whether there exists a Deterministic Turing Machine M Such that both P and M accept the same languge.
III. Given a deterministic Turing Machine M, wheather there exists a Non Deterministic PDA P such that both P and M accept the same languge.
IV. Given a regular languge L, whether the complement of L is a DCFL
Which of the above problems are decidable ?

Q. Consider the following statements:
I. There exists a non deterministic context free language whose reversal is DCFL.
II. There exists a non regular CSL whose Kleene closure is regular.
Which of the above statements are true ?

Q. Consider the following problems L(G) denotes the language generated by a grammar G.L(M) denotes the language accepted by a machine M.
I. For an unrestricted grammar G and a string w, whether w

ϵ

L(G).
II. Given a Turing Machine M, whether L(M) is regular.
III. Given two grammars

G_{1} a n d G_{2},

(G_{1}) = L (G_{2})

.
IV. Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language.
Which one of the following statements is correct?

Q. Which regular expression best describes the language accepted by the non-deterministic automation below?

View More

Join BYJU'S Learning Program

similar_icon

Related Videos

lock

States of Matter

Watch in App

Join BYJU'S Learning Program

CrossIcon