Let L1 be regular language, L2 be a deterministic context free language and L3 a recursively enumerable language, but not recursive. Which one of the following statements is false?

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

A

I only

B

III only

C

III and IV only

D

I and IV only

Which of the following statement(s) is/are FALSE? (i) There exists a recursively enumerable language whose complement is not recursively enumerable. (ii) If a language L is recursive, then its complement is NOT recursive.

A

Neither (i) nor (ii)

B

Both (i) and (ii)

C

Only (ii)

D

Only (i)

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

A

I, II and IV only

B

I and III only

C

II and IV only

D

I only

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

A

I, II and IV only

B

II and III only

C

I and IV only

D

III and IV only

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?

A

W can be recursively enumerable and Z is recursive.

B

W can be recursive and Z is recursively enumerable.

C

W is not recursively enumerable and Z is recursive.

D

W is not recursively enumerable and Z is not recursive.

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

A

L2 – L1 is recursively enumerable

B

L1 – L3 is recursively enumerable

C

L2 ∩ L1 is recursively enumerable

D

L2 ∪ L1 is recursively enumerable

Assume statements S1 and S2 defined as: S1: L2-L1 is recursive enumerable where L1 and L2 are recursive and recursive enumerable respectively. S2: The set of all Turing machines is countable. Which of the following is true?

A

S1 is correct and S2 is not correct

B

Both S1 and S2 are correct

C

Both S1 and S2 are not correct

D

S1 is not correct and S2 is correct

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?

A

I only

B

II only

C

I and III only

D

III only

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

A

I and IV only

B

II and III only

C

II, III and IV only

D

III and IV only

Choose the correct option: Statement: If L1 and L2 are recursively enumerable languages over S, then the following is/are recursively enumerable.

A

L1 U L2

B

L2 ∩ L2

C

Both L1 U L2 and L2 ∩ L2

D

None of the mentioned

Let L1 be regular language, L2 be a deterministic context free language and L3 a recursively enumerable language, but not recursive. Which one of the following statements is false?

Related Questions