Register

GATE CSE 2017 Set 2 | Question: 04

• retagged by
11,670 views
41 votes
41 votes

Let $L_1, L_2$ be any two context-free languages and $R$ be any regular language. Then which of the following is/are CORRECT?

  1. $L_1 \cup L_2$ is context-free
  2. $\overline{L_1}$ is context-free
  3. $L_1 - R$ is context-free
  4. $L_1 \cap L_2$ is context-free
  1. I, II and IV only
  2. I and III only
  3. II and IV only
  4. I only
• retagged by
User Avatar

6 Answers

1 votes
1 votes

1) CFLs are closed under union.

2)CFLs are not enclosed under complementation and intersection.

3) L1−R = L1 intersection R' = L1 intersection R So CFL on intersection with Regular it will be CFL

So Option B

User Avatar
0 votes
0 votes

Only I and III are correct , so option B is correct.

  1. CFG are not closed under complement. and  IV. CFG are not closed under intersection.
User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

77 votes
77 votes
12 answers
3
Arjun asked Feb 14, 2017
28,371 views
GATE CSE 2017 Set 2 | Question: 39
Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$ ... $\emptyset$ $\{q_0, q_1, q_3\}$ $\{q_0, q_1, q_2\}$ $\{q_0, q_2, q_3 \}$
Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$-NFA whose transition table is given below:$$\...
User Avatar
Link Copied!