Une expression régulière peut-elle être infinie?

Je sais que les langages qui peuvent être définis à l'aide d'expressions régulières et ceux reconnaissables par DFA / NFA (automates finis) sont équivalents. De plus, aucun DFA n'existe pour la langue . Mais il peut encore être écrit en utilisant des expressions régulières (pour cette question toute langue non régulière peut être) comme . Mais nous savons que chaque langue qui a une expression régulière a un DFA qui le reconnaît (contradiction avec ma déclaration précédente). Je sais que c'est une chose banale, mais la définition de l'expression régulière inclut-elle la condition qu'elle soit finie? $\{0^n1^n|n \ge 0\}$ $\{ \epsilon \} \cup \{01\} \cup \{0011\}......$

formal-languages regular-languages regular-expressions sashas
la source

Vous avez déjà répondu à votre propre question: si REG CFL, ces termes ne peuvent pas être des expressions régulières.

⊊

$\subsetneq$

Raphael

Juste une remarque: si nous supprimons l'exigence que DFA / NFA soit fini, nous pouvons construire un automate pour accepter

{0^{n} 1^{n} ∣ n \geq 0}

$\{0^n1^n\mid n\geq0\}$ .

Comme point de terminologie, le mot «automates» est le pluriel de «automate». Il n'y a pas de mot «automates» - vous ne pouvez pas le rendre plus pluriel qu'il ne l'est déjà. (les automates sont corrects en tant que possessifs mais pas en tant que pluriel)

chasly du Royaume-Uni

Réponses:

Si les expressions régulières pouvaient être infinies, alors n'importe quelle langue aurait été régulière.

Compte tenu de la langue , on peut toujours définir l'expression régulière , qui définit exactement . (Exemple: l'expression régulière définit .) $L=\{w_1, w_2, \ldots\}$ $R = w_1 + w_2 + \cdots$ $L$
$R_1 = \epsilon+0+1+00+01+10+11+\cdots$ $L_1=\{0,1\}^*$

Nous savons que certaines langues ne sont pas régulières, ce qui montre que les expressions régulières infinies décrivent une classe de langues plus large que les expressions régulières finies.

A sonné.
la source

J'adore cette réponse, car elle dit non seulement que les expressions régulières infinies sont différentes, mais que le concept dans son ensemble n'a pas de sens.

jmite

Une déclaration plus succincte du point que j'ai enterré dans mon deuxième paragraphe, et donc plus clair.

Davislor

Mais cela se termine par une pure tautologie. Pourquoi ne considérons-nous pas toutes les langues comme régulières alors, si elles ont ce formulaire? Les choses que nous faisons avec les regex ne fonctionnent plus. Nous ne pouvons pas construire une machine à états par un algorithme inductif car il ne se termine jamais et a des états infinis. Nous ne pouvons pas comparer à tout dans la liste et rejeter si rien ne correspond. Et nous ne pouvons pas représenter physiquement la liste de toute façon. (Les listes que nous pouvons générer par ordinateur sont les langues décidables.) Nous pouvons prouver des choses en utilisant le fait que chaque langue a cette forme, mais pas le genre de choses que nous connaissons sur les expressions régulières.

Davislor

@jmite "n'a pas de sens" ou un cas spécial?

BAR du

@BAR n'a pas de sens, car dans la classe des langages, décrit par des expressions régulières infinies n'est que c'est-à-dire l'ensemble de tous les langages. Nous n'obtenons pas une classe de langues comme vous le faites avec les RE finis, les CFG ou même les machines de Turing.

Σ

$\Sigma$

2^{Σ}

$2^{\Sigma}$

jmite

Oui, ça doit être fini. Imaginez que vous ayez cet ensemble infini de correspondances possibles, et votre entrée est 011. Pourriez-vous jamais le rejeter? Souhaitez-vous jamais manquer de matchs pour vérifier?

Y a-t-il un langage qui, selon cette définition, ne serait pas régulier ? Qu'en est-il de l'ensemble de toutes les paires de programmes et d'entrées de sorte que le programme donné s'arrête sur l'entrée donnée?

Maintenant, si vous aviez un programme qui énumère les chaînes dans une langue dans un ordre lexicographique ...

Mise à jour

Pour clarifier un peu en fonction des commentaires dans les commentaires, la raison pour laquelle toutes les langues de ce formulaire ne sont pas régulières est par définition. Si, par exemple, vous recherchez la preuve du théorème de Kleene, cela dépend du fait qu'une expression régulière doit être finie pour prouver qu'elle génère une machine à états finis.

Pourquoi définissons-nous le langage «normal» de cette façon? Parce que chaque langue formelle est un sous-ensemble des chaînes d'un alphabet, et chaque ensemble de chaînes peut être exprimé comme une union de singletons, donc si nous appelions n'importe quel ensemble de chaînes une langue «régulière», la langue régulière ne serait qu'un synonyme de la langue . Ce n'est pas une définition très utile, d'autant plus que nous ne pouvons pas réellement l'implémenter dans le matériel ou le logiciel. Nous ne pouvons pas stocker une liste infinie arbitraire n'importe où ni construire une machine à états infinis.

Comme je l'ai laissé entendre, cependant, si vous avez un moyen d'énumérer toutes les chaînes dans une langue dans l'ordre, vous pouvez construire un décideur à partir de cela (acceptez lorsque vous voyez cette chaîne exacte, rejetez lorsque vous rencontrez une chaîne qui vient après celle que vous recherche) et vice versa (pour chaque chaîne dans l'ordre, exécutez-la dans le décideur et affichez-la si et seulement si elle est acceptée). Donc, si nous considérions chaque langue énumérable comme régulière , chaque langue décidable serait «régulière» et nous aurions besoin d'un nouveau terme pour les langues reconnues par les machines à états finis et leurs encodages équivalents comme expressions finies.

Davislor
la source

Cette réponse est fausse. Le seul fait qu'une certaine représentation d'une langue ne se prête pas à la construction d'un décideur algorithmique de manière naïve n'implique pas que cette représentation est fausse; il pourrait y avoir d'autres approches. En fait, chaque langue décidable a une représentation de la forme proposée par sasha! En bref, vous commettez l'erreur "Je ne vois pas comment, donc ça doit être impossible".

Raphael

@Raphael: Veuillez considérer les implications de votre déclaration, " chaque langue décidable a une représentation de la forme proposée par Sasha!" C'est d'ailleurs ce que je disais dans ma réponse. La question était: toutes les langues de cette forme sont-elles définies comme régulières? Eh bien, chaque langue décidable est-elle régulière? (Et, comme je l'ai montré, certains indécidables aussi?) Serait-ce une définition utile de «régulier»?

Davislor

De plus, loin de tromper qu'un décideur pour une liste infinie de chaînes ne peut pas être fait, ma dernière phrase était un indice sur la façon dont cela pourrait être fait: si la liste des chaînes est bien ordonnée, vous pouvez en rejeter une dès que possible lorsque vous rencontrez une chaîne devant elle dans la commande. Cependant, une machine à états finis ne peut pas le faire car elle ne peut pas représenter tous les états d'avoir comparé à chaque chaîne de la liste infinie, et les expressions régulières non plus. S'ils le pouvaient, ils seraient suffisamment puissants pour reconnaître toutes les langues décidables.

Davislor

Supposons que les expressions régulières soient infinies.

Ainsi le langage défini par {ϵ} ∪ {01} ∪ {0011} ... sera régulier. Pour chaque langue régulière, il existe un NFA. Une façon d'obtenir ce NFA serait d'avoir des NFA individuels pour chacun des {ϵ}, {01}, {0011} ... et de les combiner en utilisant ϵ transitions. Puisqu'il existe des expressions régulières distinctes infinies, nous aurons besoin de sous-NFA infinis pour être combinés. Cependant, NFA ne peut avoir qu'un nombre fini d'états (définition de NFA).

Il n'existe donc pas de NFA qui puisse définir un langage défini par l'union d'expressions régulières infinies, ce qui implique que le langage n'est pas régulier.

Ainsi, aucune expression régulière ne peut définir le même langage que le langage défini par l'union d'expressions régulières infinies.

Ainsi, les expressions régulières ne peuvent avoir que des expressions finies.

Anurag Peshne
la source

Vos "expressions régulières infinies" définissent alors une autre classe de langages, pas des langages réguliers. En fait, ils sont capables de définir n'importe quel langage, ce qui est tout à fait inintéressant (ils ne sont pas finis, donc difficiles à travailler; et ils peuvent tout faire, donc rien à étudier en termes de limitations).

vonbrand