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 $\mathrm{\Sigma }=\{0,1\}$ zijn. De taal $L_1=\{0^n{1}^n\mid n\ge 0\}$ is contextvrij maar niet regulier. Ze is contextvrij omdat ze wordt gegenereerd door de contextvrije grammatica met de regels $S\to 0S1$ en $S\to ϵ$. Dat ze niet regulier is kan aangetoond worden met behulp van het pomplemma.
• Laat het alfabet $\mathrm{\Sigma }=\{a,b,c\}$ zijn. De taal $L_2=\{w\in {\mathrm{\Sigma }}^{*}\mid {\mathrm{\#}}_a(w)\ne {\mathrm{\#}}_b(w)\text{ of }{\mathrm{\#}}_a(w)\ne {\mathrm{\#}}_c(w)\}$ is contextvrij (waar ${\mathrm{\#}}_a(w)$ het aantal $a$'s in het woord $w$ aangeeft). Het complement van $L_2$ is echter de taal $L_2^c=\{w\in {\mathrm{\Sigma }}^{*}\mid {\mathrm{\#}}_a(w)={\mathrm{\#}}_b(w)={\mathrm{\#}}_c(w)\}$, en die taal is niet contextvrij.

Afsluiteigenschappen

Contextvrije talen zijn afgesloten onder de volgende bewerkingen:

• vereniging: als $L_1$ en $L_2$ contextvrije talen zijn, dan is ook $L_1\cup L_2$ een contextvrije taal;
• concatenatie: als $L_1$ en $L_2$ contextvrije talen zijn, dan is ook $L_1{L}_2=\{w_1{w}_2\mid w_1\in L_1,w_2\in L_2\}$ een contextvrije taal;
• Kleene-ster: als $L$ een contextvrije taal is, dan is ook $L^{*}=\{w_1\dots w_n\mid w_1,\dots ,w_n\in L\}$ een contextvrije taal;
• toepassing van homomorphismen en inverse homomorphismen: als $L$ een contextvrije taal is en $\phi$ een homomorphisme, dan zijn ook $\phi (L)$ en ${\phi }^{-1}(L)$ 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 $L$ een contextvrije en $R$ een reguliere taal is, dan is $L\cap R$ 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 $L$ en een woord $w$, geldt $w\in L$. Als $L$ gegeven is als contextvrije grammatica, kan het woordprobleem met het CYK-algoritme in $O(n^3)$ opgelost worden, waar $n$ de lengte van het invoerwoord $w$ is.
• Het leegteprobleem: gegeven een contextvrije taal $L$, beslis of $L=\mathrm{\varnothing }$.
• Het eindigheidsprobleem: gegeven een contextvrij taal $L$, beslis of $L$ oneindig veel woorden bevat.

Het equivalentieprobleem (gegeven contextvrije talen $L_1$ en $L_2$, beslis of $L_1=L_2$) is echter voor contextvrije talen niet beslisbaar.