Nielit Scientist-B CS 4-12-2016
April 5, 2025Nielit Scientist-B CS 4-12-2016
April 5, 2025Nielit Scientist-B CS 4-12-2016
| Question 3 |
| L1-L2 is not context free | |
| L1 intersection L2 is context free | |
| ~L1 is context free | |
| Both (A) and (C) |
L1-L2 means L1 intersection L2(complement) == CSL Intersect (regular complement)
Since regular is closed under complement hence regular complement= regular
So it is equal to CSL intersect regular which is equal to CSL
Option A says L1-L2 is not context free . Now as we get L1-L2 is CSL and every context free is also CSL, so L1-L2 can be CFL also.
Hence A is false.
Please note closure property gives worst case possibility Means CSL intersect regular is CSL it means in worst case it is CSL and hence it can be regular as well as CFL also but in worst case it must be CSL.
Similarly with other options
L1-L2 means L1 intersection L2(complement) == CSL Intersect (regular complement)
Since regular is closed under complement hence regular complement= regular
So it is equal to CSL intersect regular which is equal to CSL
Option A says L1-L2 is not context free . Now as we get L1-L2 is CSL and every context free is also CSL, so L1-L2 can be CFL also.
Hence A is false.
Please note closure property gives worst case possibility Means CSL intersect regular is CSL it means in worst case it is CSL and hence it can be regular as well as CFL also but in worst case it must be CSL.
Similarly with other options