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