INDICE
TEMA 8.- PROPIEDADES DE LOS LENGUAJES LIBRES DEL CONTEXTO
LEMA
DE BOMBEO
PROPIEDADES
DE CLAUSURA DE LOS LENGUAJES LIBRES DE CONTEXTO
INDICE
TEMA 8.- PROPIEDADES DE LOS LENGUAJES LIBRES DEL CONTEXTO
LEMA
DE BOMBEO
PROPIEDADES
DE CLAUSURA DE LOS LENGUAJES LIBRES DE CONTEXTO
LEMA
DE BOMBEO
LEMA 1.-(Lema de Bombeo para lenguajes libres de contexto):
Sea L un
lenguaje libre de contexto o de tipo 3.
Entonces, existe una constante
n, que depende solo de L, tal que,
si z∈
L y |z|³
n, z se puede escribir de la forma z=vuwxy de forma que:
| 1. | |ux|&ge 1 | |||
| 2. | |uwx|≤ n, y | |||
| 3. | i≥ 0 vuiwxiy∈ L |
IMPORTANTE:
El lema de bombeo no es una
condición suficiente, es solo necesario. Así si
un lenguaje verifica la condición del lema no podemos garantizar
que sea libre de contexto.
|
|
 |
PROPIEDADES
DE CLAUSURA DE LOS LENGUAJES LIBRES DE CONTEXTO
TEOREMA 1.-
Los lenguajes libres de contexto son cerrados para las operaciones:
 unión |
||
| concatenación |
||
| clausura |
TEOREMA 2.-
La clase de los lenguajes libres de contexto no es cerrada para la intersección.
COROLARIO 1.-
La clase de lenguajes libres de contexto no es cerrada para el complementario.
|
|
|