Quels sont les ensembles possibles de longueurs de mots dans une langue régulière?

15

Étant donné un langage , définissez l'ensemble de longueur de comme l'ensemble de longueurs de mots dans : L L L S ( L ) = { | u |LLL

LS(L)={|u|uL}

Quels ensembles d'entiers peuvent être l'ensemble de longueurs d'une langue régulière?

Gilles 'SO- arrête d'être méchant'
la source

Réponses:

14

Premièrement, une observation qui n'est pas cruciale mais pratique: l'ensemble S d'ensembles d'entiers qui sont LS(L) pour un langage régulier L sur un alphabet non vide UNE ne dépend pas du choix de l'alphabet. Pour voir cela, considérons un automate fini qui reconnaît L ; les longueurs des mots qui sont dans L sont les longueurs des chemins sur l'automate vu comme un graphe sans étiquette de l'état de départ à tout état accepté. En particulier, vous pouvez renommer chaque flèche en une et obtenir une langue régulière avec la même longueur définie sur l'alphabet{une} . Inversement, siL est une langue régulière sur un alphabet à un élément, il peut être injecté trivialement dans un alphabet plus grand, et le résultat est toujours une langue régulière.

Par conséquent, nous recherchons les ensembles de longueurs possibles pour les mots sur un alphabet singleton. Sur un alphabet singleton, la langue est la longueur définie en unaire: LS(L)={nNunenL} . Ces langues sont appelées langues unaires.

Laissez - L un langage régulier, et d' envisager un automate fini déterministe (DFA) qui reconnaît L . L'ensemble des longueurs de mots de L est l'ensemble des longueurs de chemins dans le DFA vu comme un graphe orienté qui commence à l'état de début et se termine dans l'un des états d'acceptation. Un DFA sur un alphabet à un élément est assez docile (les NFA seraient plus sauvages): c'est soit une liste finie soit une liste circulaire. Si la liste est finie, numérotez les états de 0 à h suivant l'ordre de la liste; s'il est circulaire, numérotez les états de 0 à h suivant le début de la liste, et h à h+r long de la boucle.

automates en forme de liste

Soit F l'ensemble des indices des états acceptés jusqu'à h , et g l'ensemble des indices des états acceptés de h à h+r . alors

LS(L)=F{kr+XXg,kN}

Inversement, soit h et r deux entiers et F et g deux ensembles finis d'entiers tels que XF,Xh et Xg,hXh+r . Alors l'ensemble LF,g,r={unekr+XXg,kN}est un langage régulier: c'est le langage reconnu par le DFA décrit ci-dessus. Une expression régulière qui décrit ce langage estuneFuneg(uner) .

Pour résumer en anglais, les ensembles de longueurs des langues régulières sont les ensembles d'entiers qui sont périodiques¹ au-dessus d'une certaine valeur .

¹ Pour conserver une notion bien établie , périodique signifie la fonction caractéristique de l'ensemble (qui est une fonction N{Funelse,true} que nous élevons à une fonction Z{Funelse,true} ) est périodique. Périodique au-dessus d'une certaine valeur signifie que la fonction limitée à [h,+[ peut être prolongée en une fonction périodique.

Gilles 'SO- arrête d'être méchant'
la source
Votre observation sur la non-pertinence de l'alphabet suggère que le théorème de Parikh peut être appliqué. Plus précisément, vous montrez que LS (L) = LS (L ') où dans L' toutes les lettres sont réduites à un seul alphabet. Mais LS (L ') est la cartographie parikh de la langue L, qui est connue pour être semi-linéaire pour toute langue régulière.
Suresh
Belle approche! 1) Je pense que le premier paragraphe peut être remplacé en notant que les langages réguliers sont fermés contre les homomorphismes de chaînes. 2) Pour plus de clarté, vous devriez envisager de donner la deuxième partie de comme { h + k r + ( x - h ) } , modulo off-by-one-errors. 3) Qu'est-ce qu'un ensemble «périodique» d'entiers? LS(L){h+kr+(X-h)}
Raphael
1
@Suresh, Raphael (1): Je préfère énoncer la preuve de manière élémentaire, ni homomorphismes ni mappages de Parikh n'ont été mentionnés dans ma classe CS 102.
Gilles 'SO- arrête d'être méchant'
@Raphael (2) Là où vous commencez dans l'indexation n'a pas d'importance, je pourrais supprimer la condition h G , car F peut absorber autant de petits éléments que nous voulons. (3) Un ensemble qui est périodique au-dessus d'une certaine valeur est celui qui peut être mis sous la forme affichée ci-dessus. GhGF
Gilles 'SO- arrête d'être méchant'
5

Tout sous-ensemble fini peut être l'ensemble de longueurs d'un langage régulier L , car vous pouvez prendre un alphabet unaire { 0 } et définir L comme { 0 1 , , 0 n } (cela inclut la langue vide et { ε } ).{1,,n}NL{0}L{01,,0n}{ε}

Maintenant pour les ensembles infinis. Je donnerai une brève analyse, bien que la réponse finale ne soit pas assez explicite. Je ne m'étendrai pas à moins que vous ne me le demandiez, car je pense que c'est intuitif et parce que je n'ai pas beaucoup de temps maintenant.

Soit des expressions régulières générant respectivement les langages L 1 et L 2 . Il est (en quelque sorte) facile de voir quer1,r2L1L2

  • .LS(L(r1+r2))=LS(L1L2)=LS(L1)LS(L2)
  • . Ceci est noté L S ( L 1 ) + L S ( LLS(L(r1r2))=LS(L1L2)={1+2:1LS(L1),2LS(L2)} .LS(L1)+LS(L2)
  • LS(L(r1))={0}n1{i=1ni:(1,,n)(LS(L1))n}.

Ainsi, les ensembles possibles d'entiers qui peuvent être l'ensemble de longueurs d'un langage régulier sont ceux qui sont des sous-ensembles finis de ou qui peuvent être construits en prenant des sous-ensembles finis S 1 , S 2 de N et en utilisant les formules précédentes un fini nombre de fois.NS1,S2N

Ici, nous utilisons que les langages réguliers sont construits, par définition, en appliquant les règles de construction d'une expression régulière un nombre fini de fois. Notez que nous pouvons commencer avec n'importe quel sous-ensemble fini de , même si dans les expressions régulières nous commençons avec des mots de longueur 0 et 1 uniquement comme cas de base. Ceci est facilement justifié par le fait que tous les mots (finis) sont des concaténations (finies) des symboles de l'alphabet.N

Janoma
la source
Je ne vois pas de réponse définitive. (Aviez-vous l'intention de terminer votre réponse plus tard?) J'espérais une description simple des ensembles possibles et une connexion avec les automates.
Gilles 'SO- arrête d'être méchant'
La réponse finale est là: "Ainsi, les ensembles possibles d'entiers ...". Il s'agit en effet d'une description simple, bien que liée à des expressions régulières et non à des automates.
Janoma
Il existe une description plus simple qui n'implique pas de prendre un point fixe. Peut-être que cette question n'est pas aussi élémentaire que je le pensais!
Gilles 'SO- arrête d'être méchant'
Je ne pense pas que vous puissiez éviter la dernière règle, car c'est l'opérateur étoile qui peut produire des ensembles de longueurs infinis, tout comme il produit des langages infinis.
Janoma
@Gilles Vous voulez donc une forme fermée du plus petit point fixe de la solution inductive fournie par Janoma?
Raphael
2

Selon le lemme de pompage pour les langues régulières, il existe un tel qu'une chaîne x de longueur au moins égale à n puisse s'écrire sous la forme suivante: x = u v w Où les trois conditions suivantes sont réunies: | u v | < n | v | > 0 u v k w LnXn

X=uvw
|uv|<n
|v|>0
uvkwL

Cela nous donne un test pour les ensembles: un ensemble ne peut pas être l'ensemble de longueur d'un langage normal à moins que tous ses éléments ne puissent être exprimés sous la forme d'un ensemble arbitraire d'entiers non supérieur à un fixe , plus un multiple d'une valeur indéterminée m (la longueur de v ), plus une valeur finie arbitraire.nmv

En d'autres termes, il semble que les ensembles possibles de longueurs de langue pour les langues régulières soient la fermeture par rapport à l'union des ensembles (comme discuté sous EDIT et EDIT2, grâce aux commentateurs) des ensembles décrits comme suit: Pour les ensembles fixes a , b N et tous les ensembles finis S , par le lemme de pompage pour les langues régulières (merci à Gilles d'avoir signalé une erreur idiote dans ma version originale, par laquelle je définissais l'ensemble N ).

{une+bn|nN}S
une,bNSN

EDIT: Un peu plus de discussion. Certes, tous les ensembles entiers finis sont des ensembles de longueurs. De plus, l'union de deux ensembles de longueurs doit également être un ensemble de longueurs, de même que le complément de tout ensemble de longueurs (d'où l'intersection, donc la différence). La raison en est que les langues régulières sont fermées dans le cadre de ces opérations. Par conséquent, la réponse que je donne ci-dessus est (peut-être) incomplète; en réalité, toute union de tels ensembles est également la longueur d'un langage régulier (notez que j'ai abandonné l'exigence d'intersection, de complément, de différence, etc., car ceux-ci sont couverts par le fait que les langages réguliers sont fermés sous ces propriétés, comme discuté dans EDIT3; je pense que seul l'union est réellement nécessaire, même si les autres ont raison, ce qui pourrait ne pas être le cas).

bnune vient de la concaténation, et la discussion de l'union, de l'intersection, de la différence et du complément vient du + des expressions régulières (ainsi que d'autres propriétés de fermeture des langages réguliers) prouvables à partir des automates) .

EDIT3: À la lumière du commentaire de Janoma, oublions les propriétés de fermeture des ensembles de longueurs de langue dont je discute dans le premier EDIT. Étant donné que les langues régulières ont ces propriétés de fermeture et que chaque langue régulière a un DFA, il s'ensuit que le lemme de pompage pour les langues régulières s'applique à toutes les unions, intersections, compléments et différences de langues régulières, et nous allons en rester là. ; pas besoin d'en tenir compte, à l'exception de l'union, qui, selon moi, pourrait encore être nécessaire pour corriger mon original (modifié, grâce à la contribution de Gilles). Donc, ma réponse finale est la suivante: ce que je dis dans la version originale, plus la fermeture des ensembles de longueur de langue par rapport à l'union d'ensemble.

Patrick87
la source
1
{une+bnune,b,nN}SN
1
L=L(une)Σ={une,b}LNL¯N+
@Gilles Mais l'ensemble de tous les nombres naturels est un ensemble de longueur valide, non? Je ne génère pas tous les sous-ensembles de nombres naturels, non? Je suis d'accord que ce serait problématique. Edit: oh attendez, je vois ce que vous dites. Oui tu as raison. Résoudra lorsque de retour à l'ordinateur.
Patrick87
@Janoma Excellent point, devra réfléchir à la façon dont cela pourrait changer l'ensemble des choses que je définis ...
Patrick87