Existe-t-il un analogue de «régulier» pour les cordes infinies?

Considérez la séquence . Il semble "régulier" d'une manière qui, par exemple, ne l'est pas. $s_1 = (1, 0, 1, 0,\dots)$ $s_2 = (1, 2, 3, 4,\dots)$

Je ne sais pas comment formaliser cette intuition cependant. Une chose qui me saute aux yeux est que est un langage normal, et est en quelque sorte la limite des chaînes dans ce langage. $L =\{(0 1)^n\}$ $s_1$

Existe-t-il une terminologie pour considérer ces chaînes infinies? Avons-nous quelque chose d'analogue au lemme de pompage, par lequel nous pouvons affirmer qu'une telle chaîne "régulière infinie" est de la forme avec , , finie? $x y^ {\infty}z$ $x$ $y$ $z$

formal-languages regular-languages Xodarap
la source

Peut-être périodique ou éventuellement périodique .

Yuval Filmus

Pompage : Votre déclaration sur les chaînes infinies n'est guère un analogue du lemme de pompage , qui dit que les mots suffisamment longs dans une langue régulière contiennent une sous-chaîne qui peut être répétée pour donner un autre mot. Cela ne dit pas que tous les mots ont cette forme!

PJTraill

Terminologie : Vous parlez d'une chaîne étant régulière, alors que le terme régulier est normalement appliqué aux langues.

PJTraill

Réponses:

Probablement le terme le plus spécifique pour décrire votre première chaîne, $010101\dots$ est périodique . Un string $x_1x_2\dots$ (fini ou infini) est périodique s'il y en a $t$ de telle sorte que, pour tous $i$ , $x_i=x_{i+t}$ . Dans le cas de cet exemple, nous pouvons prendre $t=2$ . Une notion légèrement plus faible est qu'une chaîne est éventuellement périodique s'il y a $n$ et $t$ tel que $x_i=x_{i+t}$ pour tous $i\geq n$ .

Plus généralement, cependant, il existe un analogue direct des langues régulières, qui est le $\omega$ -langues régulières . Ceux-ci sont reconnus par les généralisations naturelles des automates finis. L'ensemble d'états est toujours fini mais le critère d'acceptation doit être modifié pour traiter des mots infinis - en particulier, nous ne pouvons pas simplement dire "Accepter si l'automate finit dans un état acceptant" car l'automate ne termine jamais de traiter son entrée infinie.

La classe d'automates la plus simple pour les mots infinis sont les automates Büchi . Ils sont définis exactement comme les automates finis auxquels vous êtes habitué, et ils acceptent leur entrée si au moins un état acceptant est visité infiniment souvent pendant l'exécution de l'automate. Une différence par rapport aux automates finis ordinaires est qu’il s’avère que les automates Büchi non déterministes sont plus puissants que les automates déterministes, et $\omega$ -les langues régulières sont celles acceptées par les automates Büchi non déterministes. D'autres critères d'acceptation raisonnables conduisent à d'autres modèles d'automates qui acceptent la même classe de langages.

Notez qu'il n'est pas tout à fait logique d'écrire $xy^\omega z$ , puisque vous ne pouvez rien avoir après une séquence infinie de $y$ s. Au moins, vous ne pouvez pas si les positions de votre chaîne sont indexées par les nombres naturels. S'ils sont indexés par des ordinaux plus grands, cela peut avoir du sens.

Je ne me souviens pas vraiment s'il y a un analogue du lemme de pompage pour $\omega$ -langues régulières. C'est un peu gênant, même si cela fait plus d'une décennie que j'ai enseigné à un diplômé sur ce genre de choses.

David Richerby
la source

Agréable. Peut-être ajouter explicitement que

ω

$\omega$ -les langues régulières sont des unions finies de langues

A B^{ω}

$AB^\omega$ , où

A, B

$A,B$ ordinaire. Je ne sais pas sur le pompage, mais il est parfois utile de noter que chaque

ω

$\omega$ -un langage régulier doit contenir une chaîne éventuellement périodique.

Hendrik Jan

J'ai toujours détesté la présentation standard du lemme de pompage pour être si sacrément obtus. En fin de compte, tout ce qu'il dit, c'est que, puisqu'il existe un ensemble fini d'états, toute chaîne avec plus de symboles qu'il y a d'états doit visiter un état deux fois pendant l'exécution de l'automate. Les symboles participant à cette boucle sont ceux que vous pouvez "pomper". Dans cette optique, il est clair qu'il y a un analogue lorsque nous passons à des chaînes infinies mais conservons des états finis; donc la question n'est pas "y a-t-il un lemme de pompage?" mais "combien plus compliqué est le lemme de pompage?".

Daniel Wagner

@DanielWagner: Wow, ouais ... la présentation standard est en effet sacrément obtuse et la vôtre le montre clairement. Merci pour cette explication!

user541686

@DanielWagner: le lemme de pompage est certainement déroutant, mais l'avantage de la présentation standard est qu'elle ne fait pas référence à la mécanique des automates, des expressions régulières ou de toute autre manière particulière de définir des langages réguliers. Il ne parle que de cordes!

Max

@Max Un avantage douteux en effet!

Daniel Wagner

Il s'agit d'un résultat de base de l'efficacité de type deux, qui, je pense, répond à votre question d'un point de vue calculable. Dans ce qui suit, nos langues ne sont constituées que de chaînes infinies. Nous désignons l'ensemble des chaînes infinies $\Sigma^\omega$ .

Théorème: si un automate réalisable se termine sur chaque chaîne infinie, alors la langue de l'automate est égale à $S\Sigma^\omega$ où $S$ est un ensemble fini de chaînes finies.

La preuve est par le lemme de Konig.

La conclusion est qu'un langage sur des chaînes infinies est soit "simple" dans un certain sens (ce qui est un fait intéressant ) soit indécidable. Toute notion non triviale de langage sur des chaînes infinies est indécidable.

Vous pouvez probablement étudier des langues moins simples si vous permettez à l'adhésion d'être semi- décidable plutôt que décidable. Cela peut toujours être considéré comme de "l'informatique" et pas seulement des mathématiques infinitaires (il s'agit de problèmes de recherche plutôt que de problèmes de décision; la semi-décidabilité est en un sens suffisante pour faire une recherche).

ogogmad
la source