Pompujący lemat dla deterministycznych języków bezkontekstowych?

Lemat pompujący dla zwykłych języków może być użyty do udowodnienia, że ​​niektóre języki nie są regularne, a lemat pompujący dla języków bezkontekstowych (wraz z lematem Ogdena) może być użyty do udowodnienia, że ​​niektóre języki nie są kontekstowe.

Czy istnieje determinujący lemat dla deterministycznych języków bezkontekstowych? To znaczy, czy istnieje lemat podobny do lematu pompującego, którego można użyć, aby pokazać, że język nie jest DCFL? Jestem ciekawy, ponieważ prawie wszystkie techniki dowodowe, które znam, aby pokazać, że język nie jest DCFL, są naprawdę skomplikowane i miałem nadzieję, że będzie łatwiejsza technika.

Nie jest pompowania Lemat specjalnie dla DCFL, pod tytułem „pompowania Lemat dla deterministycznych języków bezkontekstowych”, przez Yu Sheng; Information Processing Letters 31 (1989) 47-51, doi 10.1016 / 0020-0190 (89) 90108-7 . Z tym wyraźnym tytułem muszę przeprosić, że go przegapiłem!

Niestety, kopia internetowa ma puste miejsce w jednym ze wzorów, więc mam nadzieję, że poprawnie odtworzyłem wynik. Poniżejjest pierwszym symbolemy(gdy istnieje) lubε(jeśliy=ε).${}^{(1)}y$$y$$\varepsilon$$y=\varepsilon$

Lemma 1 (Pumping Lemma). Niech będzie DCFL. Następnie istnieje stała C dla L taka, że ​​dla dowolnej pary słów w , w ′ ∈ if$L$$C$$L$$w,w'\in$

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

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

wtedy albo (3) albo (4) jest prawdziwe:

$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$

$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$

$\{ 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 \}$nie są DCFL. Dowód wykorzystuje fakt, że każdy DCFL ma gramatykę LR (1) w normalnej formie Greibacha.