edited by
7,923 views
4 votes
4 votes

Which of the following statements is/are $\text{CORRECT}?$

  1. The intersection of two regular languages is regular.
  2. The intersection of two context-free languages is context-free.
  3. The intersection of two recursive languages is recursive.
  4. The intersection of two recursively enumerable languages is recursively enumerable.
edited by

3 Answers

5 votes
5 votes

(A)  The intersection of two recursively enumerable languages is recursively enumerable. This statement is true because REL is closed under intersection operations.


(B) the intersection of two context-free languages is context-free. This statements is false.(it may or may not be closed).

     Eg: Let $L_1={a^nb^nc^m/m,n\geq0}$

     $L_2={a^nb^mc^m/m,n\geq0}$ but

     $L_1\cap L_2={a^nb^nc^n/n\geq0}$ is non-CFL language 


(C) The intersection of two recursively languages is recursive. This is true because REC language is closed under intersection operations.


(D) The intersection of two regular languages is regular. This is also true. 

eg: $L_1=a^*$ accept the strings like $(\epsilon,a,aa,aaa,aaaa…..\infty)$

      $L_2=a^+$ accepts the strings like $(a,aa,aaa,aaaa….\infty)$

   $\therefore L_1\cap L_2=\epsilon$ which is regular language, a finite automata with initial states is accepting states.

So option $A,C,D$ is true whereas $B$ is false.

Ref: Closure Property of Language Families

2 votes
2 votes

As Context Free Language is not closed under Intersection.

Correct option is $A,C,D$

 

Answer:

Related questions

8 votes
8 votes
1 answer
1
12 votes
12 votes
3 answers
2
admin asked Feb 15, 2023
11,091 views
Which one or more of the following options guarantee that a computer system will transition from user mode to kernel mode?Function Callmalloc CallPage FaultSystem Call