Llenguatge lliure de context

De Viquipèdia
Salta a la navegació Salta a la cerca

En matemàtiques, lògica i complexitat computacional un llenguatge formal és un llenguatge lliure de context si es pot generar amb una gramàtica lliure de context.[1]

El conjunt de tots els llenguatges lliures de context és idèntic al conjunt de llenguatges acceptats per un autòmat amb pila, cosa que fa aquests llenguatges adequats per analitzar sintàcticament (parser).

A més, donada una gramàtica lliure de context, hi ha una forma directa de generar un autòmat amb pila per dita gramàtica i el seu corresponent llenguatge. L'operació contraria no és directe.

Diferents gramàtiques lliures de context poden generar el mateix llenguatge lliure de context.

Propietats de clausura[modifica]

Els llenguatges lliures de context son tancats segons les següents operacions. Sigui L i P dos llenguatges lliures de context, el llenguatge resultat també ho es:

  • la unió
  • l'invers de L
  • la concatenació
  • la clausura de Kleene
  • la imatge sota un homomorfisme
  • la imatge sota un homomorfisme
  • el desplaçament circular d'L (el llenguatge )
  • la clausura prefix d'L (el conjunt de tots els prefixos d'L)
  • el quocient L/R d'L per un llenguatge regular R

Aquesta classe de llenguatges no son tancats per la intersecció, el complement ni la diferència. Tot i això, si L és un llenguatge lliure de context i D és un llenguatge regular, llavors la intersecció i la diferència son llenguatges lliures de context.

Referències[modifica]

  1. Michael., Sipser,. Introduction to the theory of computation. 3rd ed. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.