Question Discussion & Solution

Every regular language can be produced by context free grammar and context free language can be produced by context sensitive grammar and so on. Find the context sensitive language from the given diagram

We can recognize strings of given language using one Stack. These given languages are context free, so also context sensitive. Because CFLs are closed under Union property, so union of given languages will also be Context free. But CFLs are not closed under Intersection property, so Intersection of two CFLs may not be CFL. Given L1 and If L2 are two context free languages, their intersection L1 ? L2 is not context free because we cannot identify strings of resultant language with help of one Stack: L1 = { anbncm | n > 0 and m > 0 } and L2 = { ambncn | n > 0 and m > 0 } L3 = L1 ? L2 = { anbncn | n > 0 } is not context free. So, option (a) is false. See wikipedia page for closure properties.