Contextvrije taal
In de theoretische informatica is een contextvrije taal een formele taal die door een contextvrije grammatica gegenereerd wordt. Een alternatieve karakterisering van een contextvrije taal is een taal die door een stapelautomaat geaccepteerd wordt.

In de Chomskyhiërarchie zitten de contextvrije talen tussen de reguliere en contextsensitieve talen in. Elke reguliere taal is ook een contextvrije taal en elke contextvrije taal ook een contextsensitieve. Aan de andere kant bestaan er contextvrije talen die niet regulier zijn en contextsensitieve talen die niet contextvrij zijn. Omdat contextvrije talen aan de ene kant niet zo begrensd zijn als reguliere talen, maar aan de andere kant begrensd genoeg om efficiënt herkend (geparsed) te worden, worden contextvrije talen vaak gebruikt in natuurlijke taalherkenning en in de compilerbouw.

Voorbeelden 
 Laat het alfabet  zijn. De taal  is contextvrij maar niet regulier. Ze is contextvrij omdat ze wordt gegenereerd door de contextvrije grammatica met de regels  en . Dat ze niet regulier is kan aangetoond worden met behulp van het pomplemma.
 Laat het alfabet  zijn. De taal  is contextvrij (waar  het aantal 's in het woord  aangeeft). Het complement van  is echter de taal , en die taal is niet contextvrij.

Afsluiteigenschappen 
Contextvrije talen zijn afgesloten onder de volgende bewerkingen:
 vereniging: als  en  contextvrije talen zijn, dan is ook  een contextvrije taal;
 concatenatie: als  en  contextvrije talen zijn, dan is ook  een contextvrije taal;
 Kleene-ster: als  een contextvrije taal is, dan is ook  een contextvrije taal;
 toepassing van homomorphismen en inverse homomorphismen: als  een contextvrije taal is en  een homomorphisme, dan zijn ook  en  contextvrije talen.

In tegenstelling tot de reguliere talen zijn de contextvrije talen niet afgesloten onder complement, doorsnede of verschil. Ze zijn echter afgesloten onder doorsnede met reguliere talen. Dat wil zeggen: als  een contextvrije en  een reguliere taal is, dan is  een contextvrije taal.

Beslissingsproblemen 
Voor contextvrije talen (beschreven door een contextvrije grammatica of een stapelautomaat), zijn onder andere de volgende beslissingsproblemen beslisbaar:
 Het woordprobleem: gegeven een contextvrije taal  en een woord , geldt . Als  gegeven is als contextvrije grammatica, kan het woordprobleem met het CYK-algoritme in  opgelost worden, waar  de lengte van het invoerwoord  is.
 Het leegteprobleem: gegeven een contextvrije taal , beslis of .
 Het eindigheidsprobleem: gegeven een contextvrij taal , beslis of  oneindig veel woorden bevat.
Het equivalentieprobleem (gegeven contextvrije talen  en , beslis of ) is echter voor contextvrije talen niet beslisbaar.
Formele taal