An important characterization of context-free languages is captured in what is known as the Chomsky-Schützenberger theorem. It shows the intimate connection between context-free and parenthesis languages.
Theorem 1 (Chomsky-Schützenberger).
Note that the “if” part is the trivial consequence of the following facts: parenthesis languages are context-free; any homomorphic image of a context-free language is context-free; any intersection of a context-free language with a regular language is context-free.
|Date of creation||2013-03-22 18:55:40|
|Last modified on||2013-03-22 18:55:40|
|Last modified by||CWoo (3771)|