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

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 zijn 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[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 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.