in Theory of Computation recategorized by
4,732 views
10 votes
10 votes

Let $L_1$ be a regular language and $L_2$ be a context-free language. Which of the following languages is/are context-free?

  1. $L_1 \cap \overline{L_2} \\$
  2. $\overline{\overline{L_1} \cup \overline{L_2}} \\$
  3. $L_1 \cup (L_2 \cup \overline{L_2}) \\$
  4. $(L_1 \cap L_2) \cup (\overline{L_1} \cap L_2)$
in Theory of Computation recategorized by
by
2443 3624 5537
4.7k views

Subscribe to GO Classes for GATE CSE 2022

2 Answers

10 votes
10 votes
 
Best answer

Correct Answer: B,C,D


Some insights beforehand:

  • CFLs are Not Closed under Intersection:
    $L_1=\{a^nb^*c^n\},L_2=\{a^nb^nc^*\}$ , $L_1\cap L_2=\{a^nb^nc^n\}$ not a CFL
  • CFLs are Closed under Union:
    Let both of these CFLs be represented using grammars with start symbols $S_1$ and $S_2$ respectively. We define a new symbol $S^{’}$ such that $S^{’}\to S_1\mid S_2.$ Note: the resulting language may or may not be deterministic but will be context-free.
  • CFLs are Not Closed under Complementation:
    $L_1\cap L_2=\overline{\overline{L_1}\cup\overline{L_2}}$
    We know that CFLs aren’t closed under intersection but is closed under union. So it must be the case that CFLs aren’t closed under complementation.
    Example: $L=\{a^nb^nc^n\}$ not a CFL(a CSL) but, $\overline{L}$ is and in-fact can be solved using a NPDA (construct a NPDA where it checks for either $\text{Number}_a \neq \text{Number}_b$ or $\text{Number}_b\neq \text{Number}_c$ or $\text{Number}_a \neq \text{Number}_c.$ But we can’t construct one which can check $\text{Number}_a = \text{Number}_b = \text{Number}_c)$
  • Intersection or Union of a CFL and RL always gives a CFL. So it is closed under the same.

Now,

  1. $L_2$ is complemented so, needn’t be a CFL.
  2. $\overline{\overline{L_1}\cup\overline{L_2}}=L_1\cap L_2$ intersection of a CFL and RL is a CFL
  3. $L_1\cup(L_2\cup\overline{L_2})=L_1\cup(\Sigma^*)=\Sigma^*$  hence a CFL.
  4. $(L_1\cap L_2)\cup(\overline{L_1}\cap L_2)=L_2$  or it’s a union of two CFLs if you don’t bother to solve.
edited by

5 Comments

Seems fine to me @`JEET 

1
1

@Kanwae Kan

The option B which you explained in the solution is not matching with the option B of question.

kindly check once!

1
1
lol :’)
0
0

Now perfect👍

0
0
10 votes
10 votes

The options should be $b,c,d$. 

Options –

(a) The Complement of CFL is Recursive. The intersection of Recursive and Regular is Recursive.

(b) It is $L_1 \cap L_2$ and intersection of CFL and regular is CFL.

(c) It is $\Sigma^*$ itself as $L_2  \cup \bar{L_2}$ is $\Sigma^*$ and union of $\Sigma^*$ and $L_1$ is $\Sigma^*$ which is regular and thus CFL.

 (d) Solving this you will get $L_2$ which is CFL. See the image below.

We can write the $(d)$ option as,

$= (23 \cap 34) \cup (14 \cap 34)$

$= (3) \cup (4)$

$= L_2$

edited by
by
2 17 26

2 Comments

in option D both are CFL ( regular intersection with CFL)   union of two CFL is CFL
0
0
edited by

The intersection of Recursive and Regular is Recursive.

How??

Is this because Regular language is a subset of Rec. language and therefore, regular language can be written as Recursive language, and hence we can say intersection of recursive language with recursive langauge is recursive(since, recursive languages are closed under intersection.)

0
0
Answer:

Related questions