Cierre de lenguajes libres de contexto inequívocos en pre y postfix.

Deje que sea ​​un lenguaje sin contexto. Definir que es el cierre de pre y posfijo de , en otras palabras, contiene todos los 's prefijos y sufijos, y por lo tanto sí mismo. Mi pregunta: si tiene contexto y tiene una gramática no ambigua, ¿es lo mismo para ?p p c ( L ) L p p c ( L ) L L L p p c ( L $L$$ppc(L)$$L$$ppc(L)$$L$$L$$L$$ppc(L)$

Creo que este tipo de pregunta básica ya se habría resuelto en el apogeo de la teoría del lenguaje, pero no pude encontrar una referencia adecuada.

El conjunto ciertamente no tiene contexto, pero creo que puede ser inherentemente ambiguo: considere L = { a m b m c n d ∣ m , n ≥ 0 } ∪ { d a m b n c n ∣ m , n ≥ 0 $\mathit{ppc}(L)$ entonces p p c ( L ) incluye el lenguaje clásico inherentemente ambiguo L ′ = { a m b m c n ∣ m , n ≥ 0 } ∪ { a m b n c n ∣ m , n ≥ 0

$$L=\{a^mb^mc^nd\mid m,n\geq 0\}\cup\{da^mb^nc^n\mid m,n\geq 0\}\;,$$ $\mathit{ppc}(L)$ y se puede demostrar que p p c ( L ) también es intrínsecamente ambiguo por el argumento habitual (aplique el Lema de Ogden tanto a n + n ! b n c n como a n b n c n + n ! para deducir la existencia de dos árboles distintos para a n + n ! b n + n ! c n + n ! ). $$L'=\{a^mb^mc^n\mid m,n\geq 0\}\cup\{a^mb^nc^n\mid m,n\geq 0\}\;,$$ $\mathit{ppc}(L)$$a^{n+n!}b^nc^n$$a^nb^nc^{n+n!}$$a^{n+n!}b^{n+n!}c^{n+n!}$