Context-free language

Summary

A context-free language is a formal language generated by some context-free grammar. The class contains every regular language and also languages with nesting, such as $\set{a^n b^n : n \ge 0}$. Context-free languages are closed under union, concatenation and Kleene star, but not under intersection or complement. Their membership problem is decidable in polynomial time, which makes them the basis of parsing.