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?

Question

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?

I only
III only
III and IV only
I and IV only

LohaHridoy

5 views

2025-01-04 04:42

1 Answers

Related Questions

Which of following problems are undecidable I. Membership problem in context-free languages II. Whether a given context-free language is regular III. Whether a finite state automation halts on all inputs IV. Membership problem for type 0 languages?

1 Answers 4 Views

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. Symbol table is accessed only during lexical analysis and syntax analysis. II. Compilers for programming languages that support recursion necessarily need heap storage for memory allocation in the run-time environment. III. Errors violating the condition ‘any variable must be declared before its use’ are detected during syntax analysis. Which of the above statements is/are TRUE?

1 Answers 4 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

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 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 8 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

AhmedNazir · Accepted Answer · 2022-09-04T04:29:57+06:00

Option 4 : I and IV only

Properties:

Context free language is not closed under complementation.

Recursively enumerable language is not closed under complementation.

Recursively enumerable language is closed under union.

Recursive languages are closed under complementation.

Explanation:

L₁: Context-free

L₂: recursively enumerable but not recursive

Statement I:

L̅₁ (complement of L₁) is recursive → TRUE

Since context free language (L₁) is not closed under complementation. Therefore, L̅₁is not context free language.

Complement of context free grammar is context sensitive language and every context sensitive language is recursive language.

Statement II:

L̅₂ (complement of L₂) is recursive → FALSE

Since recursively enumerable language (L₂) is not closed under complementation. Therefore, L̅₂is not recursively enumerable language. If a language is not recursively enumerable then it cannot be recursive for sure. Since recursive language is subset of recursively enumerable language.

Statement III:

L̅₁ is context-free → FALSE

Since context free language (L₁) is not closed under complementation. Therefore, L̅₁is not context free language.

Statement IV: → TRUE

Since context free language (L₁) is not closed under complementation. Therefore, L̅₁is not context free language.

Complement of context free grammar is context sensitive language and every context sensitive language is recursively enumerable language.

Also, recursively enumerable language is closed under union. Therefore, L̅₁ ∪ L₂ is recursively enumerable.