Example 6.2.3: non CF intersection and complement
The languages {apbpcq| p,q 0} and {apbqcq| p,q 0} are both context-free. In fact, they are deterministic context-free. But {apbpcq| p,q 0} _ {apbqcq| p,q 0} = L1 from Example 6.2.1 which is not context-free.
Also, {apbpcq| p,q 0} _ {apbqcq| p,q 0} = _(_{apbpcq| p,q 0} ____{apbqcq| p,q 0}) = _L3 by DeMorgan's laws. But _{apbqcq| p,q 0} and _{apbqcq| p,q 0} are both context-free (complementsof deterministic context-free languages).
So L3 = _{apbpcq| p,q 0} ____{apbqcq| p,q 0} is an example of a context-free language:
Previous slide | Next slide | Back to first slide | View graphic version |