NIELIT 2018-81

Question

Identify the true statement from the given statements:

1. A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language.
2. The complement of a recursive languages is recursive
3. The complement of a context-free language is context-free

• A. Only $1$
• B. $1$ and $2$
• C. $1$, $2$ and $3$
• D. $2$ and $3$

Comments

A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language. What is the meaning of recursive subset ??  I want to know properly mathematical definition 

---

Sorry, my answer is not mathematical but analogical.

"An apple is a fruit which is an apple."

Do you think it makes sense? I suggest to go behind real meanings for GATE, TIFR, CMI, ISI questions where each sentence is supposed to have a meaning. NIELIT questions are long way from it though NIELIT aptitude questions are quite decent.

Answer 1

CFLs ARE NOT CLOSED UNDER COMPLEMENT .

OPTION B is correct.

 

Answer 2

1. True

2. True. Recursive Languages are closed under complementation.

3. False. context-free languages are not closed under complementation. Their complement is CSL.

So B is correct.

Answer 3

TRUE: A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language
TRUE: The complement of a recursive language is recursive
FALSE because The complement of a deterministic context free language is deterministic context free.