###### Theory-of-Computation

December 6, 2023###### Question 9742 – Theory-of-Computation

December 6, 2023# Theory-of-Computation

Question 1 |

_{1}is a regular language and L

_{2}is a context free language. Which one of the following languages is NOT necessarily context free?

L1. L2
| |

L1 ∪ L2 | |

L1 ∩ L2 | |

L1 − L2 |

L1. L2 => regular . CFL == CFL. CFL (as every regular is CFL so we can assume regular as CFL)

Since CFL is closed under concatenation so

CFL. CFL= CFL

Hence

Regular . CFL = CFL is true

L1 ∪ L2 => Regular ∪ CFL = CFL

Regular ∪ CFL = CFL ∪ CFL (as every regular is CFL so we can assume regular as CFL)

Since CFL is closed under union

Hence Regular ∪ CFL = CFL is true

L1 ∩ L2 => Regular ∩ CFL = CFL

Regular languages are closed under intersection with any language

I.e,

Regular ∩ L = L (where L is any language such as CFL, CSL etc)

Hence Regular ∩ CFL = CFL is true

**Please note this is a special property of regular languages so we will not upgrade regular into CFL (as we did in S1 and S2). We can directly use these closure properties.**

L1 − L2 => Regular − CFL = CFL

=> Regular − CFL = regular ∩ CFL (complement)

Since CFL is not closed under complement so complement of CFL may or may not be CFL

Hence Regular − CFL **need not be CFL**

**For ex:**

**R= (a+b+c)* and L= {a****m**** b****n**** c****k**** | m ≠ n or n ≠ k} which is CFL.**

**The complement of L = {a****n**** b****n**** c****n**** | n>0} which is CSL but not CFL.**

**So **

**R **− **L = (a+b+c)* **− **{a****m**** b****n**** c****k**** | m ≠ n or n ≠ k}**

=> **(a+b+c)* **∩ L (complement)

=> **(a+b+c)* **∩ **{a****n**** b****n**** c****n**** | n>0}**

**=> {a****n**** b****n**** c****n**** | n>0}**

**Which is CSL. Hence **Regular − CFL **need not be CFL**.

L1. L2 => regular . CFL == CFL. CFL (as every regular is CFL so we can assume regular as CFL)

Since CFL is closed under concatenation so

CFL. CFL= CFL

Hence

Regular . CFL = CFL is true

L1 ∪ L2 => Regular ∪ CFL = CFL

Regular ∪ CFL = CFL ∪ CFL (as every regular is CFL so we can assume regular as CFL)

Since CFL is closed under union

Hence Regular ∪ CFL = CFL is true

L1 ∩ L2 => Regular ∩ CFL = CFL

Regular languages are closed under intersection with any language

I.e,

Regular ∩ L = L (where L is any language such as CFL, CSL etc)

Hence Regular ∩ CFL = CFL is true

**Please note this is a special property of regular languages so we will not upgrade regular into CFL (as we did in S1 and S2). We can directly use these closure properties.**

L1 − L2 => Regular − CFL = CFL

=> Regular − CFL = regular ∩ CFL (complement)

Since CFL is not closed under complement so complement of CFL may or may not be CFL

Hence Regular − CFL **need not be CFL**

**For ex:**

**R= (a+b+c)* and L= {a****m**** b****n**** c****k**** | m ≠ n or n ≠ k} which is CFL.**

**The complement of L = {a****n**** b****n**** c****n**** | n>0} which is CSL but not CFL.**

**So **

**R **− **L = (a+b+c)* **− **{a****m**** b****n**** c****k**** | m ≠ n or n ≠ k}**

=> **(a+b+c)* **∩ L (complement)

=> **(a+b+c)* **∩ **{a****n**** b****n**** c****n**** | n>0}**

**=> {a****n**** b****n**** c****n**** | n>0}**

**Which is CSL. Hence **Regular − CFL **need not be CFL**.