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

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ó ${\displaystyle L\cup P}$
• l'invers de L
• la concatenació ${\displaystyle L\cdot P}$
• la clausura de Kleene ${\displaystyle L^{*}}$
• la imatge ${\displaystyle \varphi (L)}$ sota un homomorfisme ${\displaystyle \varphi }$
• la imatge ${\displaystyle \varphi ^{-1}(L)}$ sota un homomorfisme ${\displaystyle \varphi ^{-1}}$
• el desplaçament circular d'L (el llenguatge ${\displaystyle \{vu:uv\in L\}}$)
• 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ó ${\displaystyle L\cap D}$i la diferència ${\displaystyle L\setminus D}$son llenguatges lliures de context.

Referències

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