Um lema de bombeamento para linguagens deterministas livres de contexto?

O lema de bombeamento para idiomas regulares pode ser usado para provar que determinados idiomas não são regulares, e o lema de bombeamento para idiomas sem contexto (junto com o lema de Ogden) pode ser usado para provar que determinados idiomas não são livres de contexto.

Existe um lema de bombeamento para linguagens deterministas livres de contexto? Ou seja, existe um lema semelhante ao lema de bombeamento que pode ser usado para mostrar que um idioma não é um DCFL? Estou curioso, porque quase todas as técnicas de prova que sei mostrar que um idioma não é um DCFL são realmente complicadas, e eu esperava que houvesse uma técnica mais fácil.

Não é um Pumping Lemma especificamente para DCFL, sob o título "A Lema do Bombeamento para determinísticos contexto Grátis Idiomas", por Sheng Yu; Information Processing Letters 31 (1989) 47-51, doi 10.1016 / 0020-0190 (89) 90108-7 . Com este título explícito, devo pedir desculpas por ter perdido!

Infelizmente, a cópia on-line tem um espaço em branco em uma das fórmulas, portanto, espero ter reconstruído o resultado corretamente. Abaixoé o primeiro símbolo dey(quando existe) ouε(sey=ε).${}^{(1)}y$$y$$\varepsilon$$y=\varepsilon$

Lema 1 (Lema de bombeamento). Seja um DCFL. Em seguida, existe uma constante C para G tal que, para qualquer par de palavras w , w ' ∈ se$L$$C$$L$$w,w'\in$

(1) [?] E w ′ = x z , | x | > C e$w=xy$$w'=xz$$|x|>C$

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

então (3) ou (4) é verdadeiro:

(3) existe uma fatoração , | x 2 x 4 | ≥ 1 e | x 2 x 3 x 4 | ≤ C , de tal modo que para todos os i ≥ 0 x 1 x i 2 x 3 x i 4 x 5 y e x 1 x i 2$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$ estão em L ;$x_1x^i_2x_3x^i_4x_5z$$L$

(4) existem fatorações , y = y 1 y 2 y 3 e z = z 1 z 2 z 3 , | x 2 | ≥ 1 e | x 2 x 3 | ≤ C , de tal modo que para todos i ≥ 0 x 1 x i 2 x 3 y 1 $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$ ex1x i 2 x3z1z i 2 z3estão emG.$x_1x^i_2x_3y_1y^i_2y_3$$x_1x^i_2x_3z_1z^i_2z_3$$L$

Duas aplicações do Lema são dadas: , bem como { w ∈ { a , b } * | w = u v , | u | = | v | ,  E  v  contém um  um $\{ 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 \}$não são DCFL. A prova usa o fato de que cada DCFL possui uma gramática LR (1) na forma normal de Greibach.