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.

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 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 dL (el llenguatge ) la clausura prefix d'L (el conjunt de tots els prefixos d'''L) el quocient L/R dL per un llenguatge regular RAquesta 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

Categoria:Complexitat computacional Categoria:Llenguatges formals