Complexité de l'intersection des langues régulières en tant que grammaires hors contexte

20

Étant donné les expressions régulières , existe-t-il des limites non triviales à la taille de la plus petite grammaire sans contexte pour R 1R n ?R1,,RnR1Rn

Max
la source
??? essayer de visualiser cela. y a-t-il une astuce? l'intersection de est régulière. on peut trouver le DFA minimal (nombre d'états wrt) via des méthodes standard qui est aussi un CFG. Rn
vzn
@vzn: vous avez raison. Le problème est que ce DFA, et donc le CFG, peut être très volumineux. Je me demande si l'on peut utiliser la puissance supplémentaire des CFG pour obtenir une description plus succincte de l'intersection.
Max
conjecture non. soupçonne que chaque CFL qui reconnaît (c.-à-d. est équivalent à) un RL n'utilise pas sa pile ou peut être convertie en une qui ne fonctionne pas sans augmentation d'états, et le PDA minimal (nombre d'états wrt) est de la même taille que le minimum DFA. n'en ai jamais entendu / vu une preuve. ce n'est peut-être pas difficile? une question plus simple, existe-t-il un PDA qui reconnaît un RL plus petit que le DFA? pense pas.
vzn
@vzn: Conjecture utile, mais fausse: soit le sous-ensemble des langages Dyck sur deux types de parenthèses où la profondeur d'imbrication maximale est k . Il existe un CFG pour L k de taille O ( k ) , mais le DFA minimal (même, je pense, le NFA minimal) a la taille O ( 2 k ) . LkkLkO(k)O(2k)
Max
Les langues Dyck sont des CFL mais pas des RL ...? mais voyez que vous limitez la profondeur d'imbrication maximale ... alors alors pouvez-vous construire ce même langage avec des intersections RL? quelle est / où est la preuve que le DFA minimal est si grand? est-ce que les états ? vous ne définissez pas de critères de minimalité ou ailleurs et avez pris les états comme un cas naturel mais souvent ce n'est pas le seul. O(2k)
vzn

Réponses:

6

C'est une grande question et elle relève vraiment de mes intérêts. Je suis content que tu lui aies demandé Max.

Soit DFA avec au plus O ( n ) états chacun. Ce serait bien s'il existait un PDA avec de nombreux états sous-exponentiels qui accepte l'intersection des langues du DFA. Cependant, je suggère qu'un tel PDA pourrait ne pas toujours exister.nO(n)

Considérez la langue de copie. Maintenant, limitez-le à copier des chaînes de longueur n.

Formellement, considérons copie : = { x xn:= .{xx|x{0,1}n}

Nous pouvons représenter copie comme l'intersection de n DFA de taille au plus O ( n ) . Cependant, le plus petit DFA qui accepte n- copie a 2 états Ω ( n ) .nnO(n)n2Ω(n)

De même, si nous nous limitons à un alphabet de pile binaire, alors je soupçonne que le plus petit PDA qui accepte copie a exponentiellement de nombreux états.n

PS N'hésitez pas à m'envoyer un e-mail si vous souhaitez en discuter davantage. :)

Michael Wehar
la source
5

Je ne pense pas qu'il puisse y avoir de limites inférieures ou supérieures non triviales.
Pour les bornes inférieures, considérons le langage pour un k fixe . La taille de la plus petite grammaire sans contexte est logarithmique dans la taille de l' expression régulière de L 1 , tandis que la taille du plus petit automate pour L 1 est linéaire dans la taille de l' expression régulière de L 1 . Cette différence exponentielle reste la même si nous croisons L 1 avec d'autres langages de ce type. Pour les bornes supérieures, considérons un langage L 2 qui se compose exactement d'unL1={a2k}kL1L1L1L1
L2deBruijn-Séquence de longueur . On sait que la taille d'une plus petite grammaire pour L 2 est le pire des cas, c'est-à-dire O ( nnL2, donc la différence avec le "plus petit" automate pourL2est simplement un facteur logarithmique, proposition 1 dansO(nlogn)L2

Une borne inférieure ou supérieure générale non triviale contredirait ces résultats, car ce qui est vrai pour l'intersection de langues doit l'être pour l'intersection de 1 langue.n1

john_leo
la source
La remarque sur la taille de la plus petite grammaire pour la seule séquence deBruijn est assez intéressante. Pourriez-vous s'il vous plaît fournir une référence. Je vous remercie.
Michael Wehar
Aussi, je pourrais me tromper, mais il semble que vous n'ayez abordé le problème que pour une seule expression régulière (plutôt que comme un produit d'expressions régulières)?
Michael Wehar
n
1
Je vous remercie! Vous avez pu décrire un exemple précis. Voici une simple remarque qui conduit à l'existence de tels exemples. Soit n donné. Il y a 2 ^ n chaînes de longueur n. De plus, il n'y a pas plus de 2 ^ n machines de Turing avec au plus n / log (n) états. Par conséquent, une chaîne x de longueur n telle qu'aucune machine Turing avec moins de n / log (n) états n'accepte la langue {x}. Par conséquent, {x} est accepté par un DFA avec n états et ne peut pas être accepté par un PDA avec moins de n / log (n) états.
Michael Wehar
5

Permettez-moi d'appuyer le jugement de Michael, c'est en effet une question intéressante. L'idée principale de Michael peut être combinée avec un résultat de la littérature, fournissant ainsi une borne inférieure similaire avec une preuve rigoureuse.

nk

2k+12k+1sO(s2)O(4k)

2Ω(k/logk)

Ln={wwRw{a,b}|w|=n}wRwLn2n+1

  • ri=(a+b)ia(a+b)2(ni1)a(a+b)+(a+b)ib(a+b)2(ni1)b(a+b)1in
  • si=(a+b)a(a+b)2(ni1)a(a+b)i+(a+b)b(a+b)2(ni1)b(a+b)i1in
  • =(a+b)3n

kO(n2)

Ln2n/(2n)=2Ω(k/logk)2nnn/(2n)

O(4n)

Les références:

Hermann Gruber
la source