Theorem 6.1.1: the context-free languages are closed under the operations of union, concatenation, and Kleene closure (star).
Theorem 6.1.2: if L is context-free and R is regular, then L _ R is context-free; likewise, if L is deterministic context-free and R is regular, then L _ R is deterministic context-free.
Corollary 6.1.3: each language which differs from a context-free language by a regular language is context-free.
Previous slide | Next slide | Back to first slide | View graphic version |