Contextvrije taal

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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[bewerken]

  • Laat het alfabet \Sigma=\{0,1\} zijn. De taal L_1 = \{ 0^n 1^n \mid n \geq 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 \epsilon. Dat ze niet regulier is kan aangetoond worden met behulp van het pomplemma.
  • Laat het alfabet \Sigma=\{a,b,c\} zijn. De taal L_2 = \{ w \in \Sigma^* \mid \#_a(w) \neq \#_b(w) \text{ of } \#_a(w) \neq \#_c(w) \} is contextvrij (waar \#_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 \Sigma^* \mid \#_a(w) = \#_b(w) = \#_c(w)\}, en die taal is niet contextvrij.

Afsluiteigenschappen[bewerken]

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_1L_2 = \{ w_1w_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\ldots w_n \mid w_1,\ldots,w_n \in L \} een contextvrije taal;
  • toepassing van homomorphismen en inverse homomorphismen: als L een contextvrije taal is en \varphi een homomorphisme, dan zijn ook \varphi(L) en \varphi^{-1}(L) contextvrije talen.

In tegenstelling tot de reguliere talen zijn de contextvrije talen zijn 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[bewerken]

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=\emptyset.
  • 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.