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

11

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.

templatetypedef
źródło
2
Istnieje kilka powiązanych pytań, które mogą, ale nie muszą być istotne.
Raphael
Informatycy mogą być sadystami, ale nie wszyscy są masochistami, którzy stosują zbyt skomplikowane techniki dowodowe, w których znane są prostsze techniki ...
vonbrand
1
vonbrand: Ale każdy matematyk lub informatyk może użyć zbyt skomplikowanych technik dowodowych, jeśli prostsze nie są jeszcze znane lub nieznane.
Blaisorblade

Odpowiedzi:

9

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)yyεy=ε

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 ifLCLw,w

(1) [?] I w = x z , | x | > C iw=xyw=xz|x|>C

(2) , [?](1)y=(1)z

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

x=x1x2x3x4x5|x2x4|1|x2x3x4|Ci0 x1x2ix3x4ix5yx1x2ix3x4ix5zL

x=x1x2x3y=y1y2y3z=z1z2z3|x2|1|x2x3|Ci0 x1x2ix3y1y2iy3x1x2ix3z1z2iz3L

{aibii0}{aib2ii0}{w{a,b}w=uv,|u|=|v|, and v contains an a}nie są DCFL. Dowód wykorzystuje fakt, że każdy DCFL ma gramatykę LR (1) w normalnej formie Greibacha.

Hendrik Jan
źródło
Mam nadzieję, że możesz go użyć. Jeszcze bardziej skomplikowane jest stwierdzenie niż znany lemat pompujący.
Hendrik Jan