Which of the following decision problems are undescidable-I- Given NFAs N1 and N2- is LN1- LN2- II- Given a CFG G - N- - P- S and a string x- - does x- LG-III- Given CFGs G1 and G2- is LG1 - LG2 -IV- Given a TM M- is LM - - -

I. Disjointedness problem of regular = Decidable II. Membership of CFL's = Decidable nbsp; III. Equivalence of CFL's = Undecidable IV. Emptiness of RE lang ...

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

Byju's Answer

Which of the ...

Question

Which of the following decision problems are undescidable?

I. Given NFAs $N_{1}$ and $N_{2}$ , is $L (N_{1}) \cap L (N_{2}) = ϕ$

II. Given a CFG G = (N, $\sum$ , P, S) and a string $x ϵ \sum^{*},$ does $x ϵ L (G)$ ?

III. Given CFGs $G_{1} a n d G_{2}$ , is $L (G_{1}) = L (G_{2})$ ?

IV. Given a TM M, is $L (M) = ϕ$ ?

I and IV only

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

II and III only

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

III and IV only

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

II and IV only

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

Open in App

Solution

The correct option is C III and IV only
I. Disjointedness problem of regular = Decidable

II. Membership of CFL's = Decidable

III. Equivalence of CFL's = Undecidable

IV. Emptiness of RE language's = undecidable

So, III and IV only is correct answer.

Suggest Corrections

Similar questions

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},

whether L

(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?

C o n s i d e r t h e f o l l o w i n g p r o b l e m s o n d e c i d a b i l i t y : 1 . G i v e n a C F G G a n d a s t r i n g ω \in \sum * . d o e s ω b e l o n g s t o L (G) ? 2 . G i v e n a T u n i n g M a c h i n e T, a s t r i n g ω \in \sum * a n d a n i n t e g e r K, d o e s T a c c e p t ω w i t h i n k s t e p s ? 3 . G i v e n a T u n i n g M a c h i n e T, a s t r i n g ω \in \sum * a n d a s t a t e q \in Q (s e t o f s t a t e o f t h e T u n i n g M a c h i n e) . d o e s t h e c o m p u t a t i o n o f T o n ω v i s i t t h e s t a t e q ? T h e t o t a l n u m b e r o f d e i d a b l e p r o b l e m s a r e______.

Q. Consider the following CFG.

S \to a S b | b S a | a S | b S | a

Which of the following string cannot be generated by given CFG?

Q. Which of the following is/are undecidable?
1. G is CFG Is L(G)=

Φ

?
2.G is CFG Is L(G)=

\sum^{*}

?
3. M is a Turing machine,Is L(M) regular?
4. A is a DFA and N is an NFA.Is L(A)=L(N)?

Q. Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M.
Which of the following decision problems are undecidable?
I. Given a regular expression R and a string w,is

ω ε

L(R)?
II. Given a context-free grammar G, is L(G)=

ϕ

III. Given a context-free grammar G, is L(G) =

\sum^{*}

for some alphabet

\sum

?
IV. Given a Turing machine M and a string

ω

, is

ω ε

L(M)?

Join BYJU'S Learning Program

Which of the following decision problems are undescidable? I. Given NFAs N1 and N2, is L(N1)∩L(N2)=ϕ II. Given a CFG G = (N, ∑, P, S) and a string xϵ∑∗, does xϵL(G)? III. Given CFGs G1andG2, is L(G1)=L(G2) ? IV. Given a TM M, is L(M)=ϕ ?

The correct option is C III and IV onlyI. Disjointedness problem of regular = Decidable II. Membership of CFL's = Decidable III. Equivalence of CFL's = Undecidable IV. Emptiness of RE language's = undecidable So, III and IV only is correct answer.

The correct option is C III and IV only
I. Disjointedness problem of regular = Decidable

II. Membership of CFL's = Decidable

III. Equivalence of CFL's = Undecidable

IV. Emptiness of RE language's = undecidable

So, III and IV only is correct answer.