Un lemme de pompage pour des langages déterministes sans contexte?

11

Le lemme de pompage pour les langues régulières peut être utilisé pour prouver que certaines langues ne sont pas régulières, et le lemme de pompage pour les langues sans contexte (avec le lemme d'Ogden) peut être utilisé pour prouver que certaines langues ne le sont pas.

Existe-t-il un lemme de pompage pour les langages déterministes sans contexte? Autrement dit, existe-t-il un lemme semblable au lemme de pompage qui peut être utilisé pour montrer qu'une langue n'est pas un DCFL? Je suis curieux parce que presque toutes les techniques de preuve que je connais pour montrer qu'un langage n'est pas un DCFL sont vraiment compliquées, et j'espérais qu'il y avait une technique plus facile.

templatetypedef
la source
2
Il existe des questions connexes qui peuvent être pertinentes ou non.
Raphael
Les informaticiens peuvent être des sadiques, mais ils ne sont pas tous des masochistes qui utilisent des techniques de preuve trop compliquées là où des plus simples sont connues ...
vonbrand
1
vonbrand: Mais tout mathématicien ou informaticien pourrait utiliser des techniques de preuve trop compliquées si les plus simples ne sont pas encore connues ou inconnues de lui.
Blaisorblade

Réponses:

9

Il existe un lemme de pompage spécifiquement pour DCFL, sous le titre "Un lemme de pompage pour des langues déterministes sans contexte", par Sheng Yu; Lettres de traitement de l'information 31 (1989) 47-51, doi 10.1016 / 0020-0190 (89) 90108-7 . Avec ce titre explicite, je dois m'excuser de l'avoir manqué!

La copie en ligne a malheureusement une place vide dans l'une des formules, j'espère donc avoir reconstruit correctement le résultat. Au dessous de(1)yyεy=ε

LCLw,w

w=xyw=xz|x|>C

(2) (1)y=(1)z

alors (3) ou (4) est vrai:

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}ne sont pas DCFL. La preuve utilise le fait que chaque DCFL a une grammaire LR (1) sous forme normale de Greibach.

Hendrik Jan
la source
J'espère que vous pourrez l'utiliser. Il est encore plus compliqué à énoncer que le lemme de pompage connu.
Hendrik Jan