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

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

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?

A

S1 and S2

B

S3 and S4

C

S2 and S3

D

S1 and S4

Which of the following statement(s) is/are TRUE? (i) The family of context-free languages are the proper subset of the family of regular languages. (ii) The family of recursive languages is a proper subset of the family of recursively enumerable languages.

A

Both (i) and (ii)

B

Only (i)

C

Neither (i) nor (ii)

D

Only (ii)

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)

Study the accompanying Venn diagram that represents groups of persons speaking five different languages as follows. Oblong circle = Marathi ; Rectangle = Kannada, Circle = English, Triangle = Gujarati, Equilateral quadrangle = Hindi Using above information select the false statement/s from following list. (a) Area c represent persons speaking 5 languages but area d represents persons speaking 4 languages only. (b) Areas b and d represent persons speaking same number of languages. (c) Areas f, b and e represent persons speaking same languages. (d) Areas g and h represent persons who speak two languages only.

A

Both (a) and (b)

B

None

C

All but (c)

D

None but (c)

United Nations has declared the year 2019 as 'Indigenous Languages Year'. The purpose is : (a) To protect the Indigenous Languages in the world. (b) To create consciousness about decaying Indigenous Languages. (c) Resurrection of declining these languages. (d) To realise the contribution of these languages to the world cultural diversity. Which of the above purpose/purposes is/are correct ?

A

(a) only

B

(b) and (c) only

C

(a), (b) and (c) only

D

All are correct

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

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

Recursively enumerable languages are not closed under ______________

A

Union

B

Intersection

C

Complementation

D

Concatenation

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

Related Questions