search
Log In
1 vote
401 views

 

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
edited by
401 views
0

3 Answers

5 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 $\sum$ itself as $L_2  \cup \bar{L_2}$ is $\sum$ and union of $\sum$ and $L_1$ is $\sum$ 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
0
in option D both are CFL ( regular intersection with CFL)   union of two CFL is CFL
1 vote

Given : $L_1$= Regular language

$L_2$=CFL

     A) $L_1\cap \bar L_2$: as we know that CFL is not closed under complement operation. CFL complement is REC.

           therefore Reg  $\cap$ $\overline{CFL}$ =REC which is not CFL.

           hence option A is wrong here.

     B)  $\overline{(\bar L_1\cup \bar L_2)}$: this can be written as $\overline{\overline{L_1}}\cap\overline{\overline{L_2}}\implies L_1\cap L_2$.

           hence Regular $\cap$ CFL is CFL because CFL is closed with regular intersection.

            option $B$ is correct.

     C) $L_1\cup(L_2\cup \bar L_2)$: CFL complement is REC language.

           CFL$\cup$ REC is REC language and union with regular language is REC which is not CFL.

          so option $C$ is false here.

     D) $(L_1\cap L_2)\cup(\bar L_1\cap L_2)$; This can be written as:

          (regular $\cap$ CFL)$\cup$( Regular $\cap$ CFL)

         $\implies$ (regular $\cap$ CFL)= CFL, (Regular $\cap$ CFL)=CFL

        $\implies$ CFl$\cup $CFL=CFL 

Option $D$ is correct.

$\therefore$ Option $B$ and $D$ is correct.

Ref: closure-property-of-language-families

0
@Hira C is given as CFL in official key but I totally agree with you reasoning. @Arjun Sir can you please shed some light here?
0 votes

B,C,D
 



Some insights beforehand:

 

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

 

Closed under Union:
Let both of these CFLs be represented using grammars with start symbols $S_1$ and $S_2$, we define a new symbol $S^{’}$ such that $S^{’}\to S_1/S_2$ note, we definitely have a NPDA but could be represented under DPDA if the language allows it to be(2 RLs).

 

Not Closed under Complementation:

$L_1\cap L_2=\overline{\overline{L_1}\cup\overline{L_2}}$

We know that intersection isn’t  closed under context free languages and union is closed under CFL(NPDA) so it must be the case that complementation isn’t closed under CFL.
Example: $L=\{a^nb^nc^n\}$ not a CFL but, $\overline{L}$ is and infact can be solved using a NPDA.

 

Intersection and Union of a CFL is RL is CFL.


Now,

  1. $L_2$ is complemented so, needn’t be a CFL.
  1. $\overline{\overline{L_1}\cap\overline{L_2}}=L_1\cup L_2$ union of a CFL and RL is a CFL
  2. $L_1\cup(L_2\cup\overline{L_2})=L_1\cup(\Sigma^*)=\Sigma^*$  hence a CFL.
  3. $(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
Answer:

Related questions

2 votes
1 answer
1
394 views
For a string $w$, we define $w^R$ to be the reverse of $w$. For example, if $w=01101$ then $w^R=10110$. Which of the following languages is/are context-free? $\{ wxw^Rx^R \mid w,x \in \{0,1\} ^* \}$ $\{ ww^Rxx^R \mid w,x \in \{0,1\} ^* \}$ $\{ wxw^R \mid w,x \in \{0,1\} ^* \}$ $\{ wxx^Rw^R \mid w,x \in \{0,1\} ^* \}$
asked Feb 18 in Theory of Computation Arjun 394 views
2 votes
1 answer
2
287 views
​​​​​​​Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string $\epsilon$ is divisible by three. $(0+1(01^*0)^*1)^*$ $(0+11+10(1+00)^*01)^*$ $(0^*(1(01^*0)^*1)^*)^*$ $(0+11+11(1+00)^*00)^*$
asked Feb 18 in Theory of Computation Arjun 287 views
1 vote
1 answer
3
339 views
Consider the following sets, where $n \geq 2$: $S_1$: Set of all $n \times n$ matrices with entries from the set $\{ a, b, c\}$ $S_2$: Set of all functions from the set $\{0,1,2, \dots, n^2-1\}$ to the set $\{0, 1, 2\}$ Which of the following ... to $S_2$ There exists a surjection from $S_1$ to $S_2$ There exists a bijection from $S_1$ to $S_2$ There does not exist an injection from $S_1$ to $S_2$
asked Feb 18 in Set Theory & Algebra Arjun 339 views
0 votes
3 answers
4
697 views
In the context of compilers, which of the following is/are $\text{NOT}$ an intermediate representation of the source program? Three address code Abstract Syntax Tree $\text{(AST)}$ Control Flow Graph $\text{(CFG)}$ Symbol table
asked Feb 18 in Compiler Design Arjun 697 views
...