Llenguatge lliure de context
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]- ↑ Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.