Question

Prove that the language A\B = {w: wx ∈ A, X ∈ B}, where A is a CFL and B is regular is a CFL.

Answer 1

The given language is a standard Quotient operation. For clarity, consider the following example to understand the operation before proceeding to the proof:

• Since A is a CFL and B is a Regular language, A\B is CFL as context free languages are closed under Quotient operation with Regular languages.
• Proof can be given as:

• B is a part of wx ,as x∊B And wx∊A

• Now, L\R (or A\B or wx\x)=CFL/Regular
• let CFL =aⁿbⁿ  and Regular= b⁴
• So, L\R= aⁿb^n-4 which is also CFL
• Hence, A\B is CFL
• Thus, proved.