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?

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

LohaHridoy

5 views

2025-01-04 04:42

1 Answers

AhmedNazir

Option 2 : I and III only

Concept: Property of context-free languages is:

Context-free languages are closed under union and difference but not closed under complementation and intersection.

Explanation:

Option 1) L1 ∪ L2 is context-free

As context-free languages are closed under union. So it is correct.

Option 2). L̅1 is context-free

L1 is a context-free language. According to the property, its complement can’t be context-free.

Option 3) L1 – R is context-free

As the difference of a context-free language with regular is context-free. So, it is correct.

Option 4) L1 ∩ L2 is context-free

It violated the context-free language property. The intersection of two CFL’s is not CFL. So, it is incorrect.

5 views Answered 2022-09-04 04:29

Related Questions

Consider the language L = {an |n ≥ 0} ∪ {anbn| n ≥ 0} and the following statements. I. L is deterministic context-free. II. L is context-free but not deterministic context-free. III. L is not LL(k) for any k. Which of the above statements is/are TRUE?

1 Answers 4 Views

Consider the following statements. I. If L1 ∪ L2 is regular, then both L1 and L2 must be regular. II. The class of regular languages is closed under infinite union. Which of the above statements is/are TRUE?

1 Answers 4 Views

Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are true I. if L4 ∈ P, then L2 ∈ P II. if L1 ∈ P or L3 ∈ P, then L2 ∈ P III. L1 ∈ P, if and only if L3 ∈ P IV. if L4 ∈ P, then L1 ∈ P and L3 ∈ P?

1 Answers 5 Views

For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true I. L̅1 (complement of L1) is recursive II. L̅2 (complement of L2) is recursive III. L̅1 is context-free IV. L̅1 ∪ L2 is recursively enumerable?

1 Answers 5 Views

Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y̅ reduces to W, and Z reduces to X̅ (reduction means the standard many-one reduction). Which one of the following statements is TRUE?

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

1 Answers 4 Views

Consider the following languages over the alphabet ∑ = {a, b, c} Let L1 = {an bn cm | m, n ≥ 0} and L2 = {am bn cn | m, n ≥ 0} Which of the following are context-free languages I. L1 ∪ L2 II. L1 ∩ L2?

1 Answers 7 Views

Consider the following sets: S1. Set of all recursively enumerable languages over the alphabet {0,1} S2. Set of all syntactically valid C programs S3. Set of all languages over the alphabet {0,1} S4. Set of all non-regular languages over the alphabet {0,1} Which of the above sets are uncountable?

1 Answers 6 Views

A library contained books in Hindi, English and several regional languages, such that the average number of books per language are 525, while the average number of books per regional language are 225. If the total number of Hindi and English books in the library is 2100 more than the total number of books in the regional languages, find the number of regional languages in which books are kept in the library.?

1 Answers 5 Views

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

Job Preparation (1125)

Admission (754)

এসএসসি (10)

এইচএসসি (5)