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 w ∈ L(R) II. Given a context-free grammar G, is L(G) = ϕ III. Given a context-free grammar G, is L(G) = ∑* for some alphabet ∑ IV. Given a Turing machine M and a string w, is w ∈ L(M) ?

I and IV only
II and III only
II, III and IV only
III and IV only

LohaHridoy

4 views

2025-01-04 04:42

1 Answers

AhmedNazir

Option 4 : III and IV only

Decidable properties of Languages:

For decidable: D

For un-decidable: U

For grammar: G

	Membership Problem w ∈ L(R)	Emptiness L(G) = ϕ	Universality L(G) = ∑*	Equality	L(G)= Regular	L(G) = Finite
Regular Language	D	D	D	D	D	D
DCFL	D	D	D	D	D	D
CFL	D	D	UD	UD	UD	D
CSL	D	UD	UD	UD	UD	UD
Recursive language	D	UD	UD	UD	UD	UD
Recursive enumerable language	UD	UD	UD	UD	UD	UD

From the above table:

Membership property of regular grammar is decidable.

Emptiness problem of context free grammar is decidable.

Universality property for context free grammar is undecidable.

Membership problem of Turing machine is undecidable.

4 views Answered 2022-09-04 04:29

Related Questions

Which of the following languages are undecidable Note that (M) indicates encoding of the Turing machine M. L1 = {<M>| L(M) = ϕ} L2 = {<M, w, q>| M on input w reaches state q in exactly 100 steps} L3 = {<M>| L(M) is not recursive} L4 = {<M>| L(M) contains at least 21 members}?

1 Answers 4 Views

In the following question below are given some statements followed by some conclusion based on those statements. Taking the given statements to be true even if they seem to be at variance from commonly known facts. Read all the conclusions and then decide which of the given conclusion logically follows the given statements. Statements: I. Some P are Q. II. Some S are R. III. No R is Q. Conclusions: I. Some S are Q. II. Some Q are P. III. Some R are S.?

1 Answers 4 Views

Consider the following statements. I. The complement of every Turing decidable language is Turing decidable II. There exists some language which is in NP but is not Turing decidable III. If L is a language in NP, L is Turing decidable Which of the above statements is/are true?

1 Answers 4 Views

Language L1 is defined by the grammar: S1 → aS1b|ϵ Language L2 is defined by the grammar: S2 → abS2|ϵ Consider the following statements: P: L1 is regular Q: L2 is regular Which one of the following is TRUE?

1 Answers 4 Views

Consider the transition diagram of a PDA given below with input alphabet ∑ = {a, b} and stack alphabet Γ = {X, Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA. Which one of the following is TRUE?

1 Answers 4 Views

Which of the following decision problems are undecidable 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 G1 and G2, is L(G1) = L(G2) IV. Given a TM M, is L(M) = ϕ?

1 Answers 4 Views

Consider the following languages L1 = {ap | p is a prime number} L2 = {anbmc2m | n ≥ 0, m ≥ 0} L3 = {anbnc2n | n ≥ 0} L4 = {anbn | n ≥ 1} Which of the following are CORRECT I. L1 is context-free but not regular. II. L2 is not context-free III. L3 is not context-free but recursive. IV. L4 is deterministic context-free?

1 Answers 5 Views

Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT I. L1 ∪ L2 is context-free II. L̅1 is context-free III. L1 – R is context-free IV. L1 ∩ L2 is context-free?

1 Answers 5 Views

Consider the following context-free grammar over the alphabet ∑ = {a, b, c} with S as the start symbol: S → abScT | abcT T → bT | b Which one of the following represents the language generated by the above grammar?

1 Answers 4 Views

In each of the following question below are given some statements followed by some conclusions. Taking the given statements to be true even if they seem to be at variance from commonly known facts, read all the conclusions and then decide which of the given conclusion logically follows the given statements. Statements: I. All big are small. II. Some small are tall. III. No tall is white. Conclusions: I. Some big are white. II. Some big are not white. III. Some small are not white.?

1 Answers 5 Views

এক্সাম দিয়ে মেধা যাচাই করুন

Job Preparation (1125)

Admission (754)

এসএসসি (10)

এইচএসসি (5)