Prouver la fermeture sous inversion de langues acceptée par les automates min-tas

16

Il s'agit d'une question complémentaire à celle- ci .

Dans une question précédente sur les machines à états exotiques , Alex ten Brink et Raphael ont abordé les capacités de calcul d'une sorte particulière de machine à états: les automates à tas min. Ils ont pu montrer que l'ensemble des langages acceptés par de telles machines ( HAL ) n'est ni un sous-ensemble ni un sur-ensemble de l'ensemble des langages hors contexte. Compte tenu de la résolution réussie et de l'intérêt apparent pour cette question, je vais poser plusieurs questions complémentaires.

Il est connu que les langages réguliers sont fermés sous une variété d'opérations (nous pouvons nous limiter aux opérations de base telles que l'union, l'intersection, le complément, la différence, la concaténation, l'étoile de Kleene et l'inversion), tandis que les langages sans contexte ont une fermeture différente propriétés (celles-ci sont fermées sous l'union, la concaténation, l'étoile de Kleene et l'inversion).

HAL est-il fermé en cas d'annulation?

Patrick87
la source
Quelles sont les utilisations de telles machines? Ou s'agit-il d'un exercice académique?
Dave Clarke
@DaveClark Eh bien, c'est surtout un exercice académique (pour autant que je sache, je viens de les inventer dans la question liée). Cependant, ils peuvent faire le calcul de la même manière que les autres machines (DFA, TM, etc.), donc peut-être qu'ils pourraient être utiles.
Patrick87
Cette question illustre pourquoi vous souhaitez avoir des grammaires accompagnant vos automates. Arr, mon cerveau!
Raphael
4
J'essayais de le prouver en utilisant un langage au format , mais cela a pris trop de temps et j'ai abandonné. Peut-être que cette idée aiderait n'importe qui. {xyy is a lexicographically sorted copy of x}
Ran G.
@RanG .: Je pense que cela devrait fonctionner. Je suis heureux d'attribuer la prime à une réponse qui prouve que la langue est en et donne un raisonnement décent que l'inversion ne l'est pas. HAL
Raphael

Réponses:

4

Considérons le langage (où # 0 ( x ) indique le nombre de zéros dans x ).

L×2={xyzx,y,z{0,1},#0(x)=#0(y) and |x|+|y|=z}
#0(x)x

Il est facile de décider utilisant une machine HAL - observez que la machine doit garder une trace de deux propriétés: le nombre de zéros dans x vs y et la longueur de x , y (vs z ). Il peut pousser un dans le tas pour chaque zéro qu'il voit dans x (puis pop plus tard pour tout zéro vu dans y ); en outre, il pousse pour tout bit en x , y (et plus tard apparaît pour tout bit de z ). Puisque tous les s sont poussés vers le bas du tas, ils n'interfèrent pas avec le comptage. Le L×2xyx,yz0x0y1x,y1z10 sert de délimiteur et peut être pratiquement ignoré.

Soit maintenant , la langue inverse. Autrement dit, L = { z y x x , y , z { 0 , 1 } , # 0 ( x ) = # 0 ( y )  et  | x | + | y | = z } Nous montrerons qu'aucune machine HAL ne peut décider LL=L×2R

L={zyxx,y,z{0,1},#0(x)=#0(y) and |x|+|y|=z}
L .

L'intuition est la suivante. Comme ci-dessus, la machine doit suivre à la fois la longueur de et le nombre de zéros en x , y . Cependant, dans ce cas, il doit les suivre simultanément . Cela ne peut pas être fait via un tas. Plus en détail, après avoir lu z , le tas contient des informations sur la longueur de | x | + | y | . lors de la lecture de y, la machine doit également conserver dans le tas le nombre de zéros de y . Cependant, ces informations ne peuvent pas interférer avec les informations que le tas possède déjà sur la longueur que nous attendons xzx,yz|x|+|y|yyxêtre. Très intuitivement, soit les informations sur le nombre de zéros seront "en dessous" des informations sur la longueur de , puis nous ne pouvons pas y accéder en lisant xxx , soit elles sont "au-dessus" de ces informations, rendant ces dernières inaccessibles, ou deux informations seront "mélangées" et deviendront vides de sens.

Plus formellement, nous allons utiliser une sorte d'argument de "pompage". Autrement dit, nous prendrons une entrée très longue et montrerons que "l'état" de la machine doit se répéter pendant le traitement de cette entrée, ce qui nous permettra de "remplacer" l'entrée une fois que la machine répète son "état".

Pour la preuve formelle, nous demandons une simplification de la structure de la machine HAL, à savoir qu'elle ne contient pas de "boucle" de -transitions 1 . Avec cette hypothèse, nous pouvons voir que pour chaque symbole d'entrée que la machine traite, le contenu du tas peut augmenter / diminuer d'au plusε1 (pour une constante c assez grande).cc

Preuve.
Supposons que décide de L et considérons une entrée suffisamment longue (disons de longueur 4 n , donc | x | = | y | = n , | z | = 2 n , en ignorant les s ci-après). Pour être concret, fixons z , y et supposons que # 0 ( y ) = n / 2 . Observez qu'il y a ( nHL4n|x|=|y|=n|z|=2nz,y#0(y)=n/2différentsxtels quezyxL(nn/2)xzyxL .

Considérez le contenu du tas immédiatement après le traitement de . Il contient au plus 3 n c symboles (où chaque symbole provient d'un alphabet fixe Γ ), selon notre hypothèse. Cependant, il existe ( nzy3ncΓ(nn/2)xsx1,x2

  1. n/2x1x2
  2. n/2xx1x2x1,x2n20.8n2x1,x2(3.5cn)|Γ||Q| différentes options pour le contenu et l'état du tas3).

It is clear that the machine must accept the word zyx1px2s, where x1p is a prefix of x of length n/2 and x2s is a suffix of x2 of the same length. Note that the number of zeros in x1px2s differs from the number of zeros in x1 and x2 (that is, from #0(y)), due to the way we chose x1 and x2, thus we reached a contradiction.

1 Does this assumption damages generality? I don't think so, but this indeed requires a proof. If someone sees how to get around this extra assumption, I'd love to know.
2 Let's fix x1 so that it's prefix (of length n/2 has exactly n/4 zeros). Recall that using Stirling's approximation we know that log(nk)nH(k/n) where H() is the Binary entropy funciton. Since H(1/4)0.81 we have (nn/4)>20.8n for large enough n.
3 Assuming alphabet Γ, there are |Γ|n different strings of length n, so if this was a stack we were screwed. However, pushing "01" into a heap is equivalent to pushing "10" - the heap stores only the sorted version of the content. The number of different sorted strings of size n is (n+1|Γ|1)n|Γ|, for a constant |Γ|.

Ran G.
la source
Nice! Will have to read the formal part again later. 1) Ad ¹: See also here. 2) The argument breaks down if we allow non-deterministic choice of the returned heap symbol (among all symbols of the same priority).
Raphael