GATE CS 2016 Set 2 Q.28 (CS Q.18): Regular Expressions, Finite Automata and Regular Languages

Consider the following types of languages: $L_1$ : Regular, $L_2$ : Context-free, $L_3$ : Recursive, $L_4$ : Recursively enumerable. Which of the following is/are TRUE?

I. $L_3 \cup L_4$ is recursively enumerable
II. $L_2 \cup L_3$ is recursive
III. $L_1^* \cap L_2$ is context-free
IV. $L_1 \cup L_2$ is context-free

I only

I and III only

I and IV only

I, II and III only

Official answer and solution

Official answer: D
From: Official GATE 2016 answer key

About the official key

All four statements are mathematically true, but the available options only include subsets. GATE official key is (D).

Note on this question

Statement IV is also mathematically true (the union of a Regular language and a Context-Free language is Context-Free). However, among the four provided options, no option includes all four statements, and official GATE key gives option (D).

Solution

Examine the closure properties of language classes in the Chomsky hierarchy.

Given language classes: $L_1$ is Regular (REG), $L_2$ is Context-Free (CFL), $L_3$ is Recursive (REC), and $L_4$ is Recursively Enumerable (RE).

Recall the standard hierarchy inclusions:

\text{REG} \subset \text{CFL} \subset \text{REC} \subset \text{RE}

Statement I: $L_3 \cup L_4$ is RE.
Since $L_3$ is recursive, it is also recursively enumerable. The class of RE languages is closed under union. Thus, $L_3 \cup L_4$ is always RE. Statement I is TRUE.

Statement II: $L_2 \cup L_3$ is REC.
Since $L_2$ is context-free, it is also recursive. The class of recursive languages is closed under union. Thus, $L_2 \cup L_3$ is always REC. Statement II is TRUE.

Statement III: $L_1^* \cap L_2$ is CFL.
Since $L_1$ is regular, $L_1^*$ is regular (closed under Kleene star). The intersection of a context-free language with a regular language is always context-free. Thus, $L_1^* \cap L_2$ is always CFL. Statement III is TRUE.

Statement IV: $L_1 \cup L_2$ is CFL.
Since $L_1$ is regular, it is also context-free. The class of context-free languages is closed under union. Thus, $L_1 \cup L_2$ is always CFL. Statement IV is mathematically TRUE.

Note on Official Answer:
All four statements (I, II, III, IV) are mathematically correct. However, because no option includes all four statements, the official GATE key awards option (D) ("I, II and III only").

Final answer

Common trap

Thinking the intersection of two CFLs is not CFL, without recognizing that $L_1^*$ is Regular (intersection of CFL with Regular is always CFL).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 2
Question: 28 of 65, printed as CS Q.18
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source