¿Un gran lema para los lenguajes deterministas sin contexto?

El lema de bombeo para los idiomas regulares se puede usar para demostrar que ciertos idiomas no son regulares, y el lema de bombeo para los idiomas sin contexto (junto con el lema de Ogden) se puede usar para demostrar que ciertos idiomas no están libres de contexto.

¿Existe un lema de bombeo para lenguajes deterministas sin contexto? Es decir, ¿hay un lema similar al lema de bombeo que se puede usar para mostrar que un idioma no es un DCFL? Tengo curiosidad porque casi todas las técnicas de prueba que conozco para mostrar que un lenguaje no es un DCFL son realmente complicadas, y esperaba que hubiera una técnica más fácil.

No es un Bombeo Lema específicamente para DCFL, bajo el título "Un bombeo Lema para deterministas del Contexto Idiomas", por Sheng Yu; Cartas de procesamiento de información 31 (1989) 47-51, doi 10.1016 / 0020-0190 (89) 90108-7 . ¡Con este título explícito debo disculparme por haberlo perdido!

Desafortunadamente, la copia en línea tiene un espacio en blanco en una de las fórmulas, por lo que espero haber reconstruido el resultado correctamente. Debajo de está el primer símbolo de (cuando existe) o (si ).${}^{(1)}y$$y$$\varepsilon$$y=\varepsilon$

Lema 1 (Lema de bombeo). Deja que sea ​​un DCFL. Entonces existe una constante para tal que para cualquier par de palabras si$L$$C$$L$$w,w'\in$

(1) [?] Y , y$w=xy$$w'=xz$$|x|>C$

(2) , [?]${}^{(1)}y = {}^{(1)}z$

entonces (3) o (4) es cierto:

(3) hay una factorización , y , tal que para todo y están en ;$x=x_1x_2x_3x_4x_5$$|x_2x_4|\ge 1$$|x_2x_3x_4|\le C$$i\ge 0$ $x_1x^i_2x_3x^i_4x_5y$$x_1x^i_2x_3x^i_4x_5z$$L$

(4) existen factorizaciones , y , y , de modo que para todos y están en .$x=x_1x_2x_3$$y=y_1y_2y_3$$z=z_1z_2z_3$$|x_2|\ge 1$$|x_2x_3|\le C$$i\ge 0$ $x_1x^i_2x_3y_1y^i_2y_3$$x_1x^i_2x_3z_1z^i_2z_3$$L$

Se dan dos aplicaciones del Lema: así como no son DCFL. La prueba utiliza el hecho de que cada DCFL tiene una gramática LR (1) en forma normal de Greibach.$\{ a^ib^i \mid i\ge 0 \} \cup \{ a^ib^{2i} \mid i\ge 0 \}$$\{ w\in\{a,b\}^* \mid w=uv, |u|=|v|, \mbox{ and } v \mbox{ contains an } a \}$