Quelle est la régularité?

Question

Il est plus d'une question de science informatique que une programmation, mais je dis que c'est le meilleur endroit de tous les sites liés à poser.

Quand j'ai découvert les expressions régulières et regardé le terme que je suppose que cette propriété de « régularité » fait référence au fait que la langue de l'expression a un motif de structure définissable. Cependant, à la lecture sur le sujet et la théorie derrière ce que j'ai appris qu'il ya des sortes de langues qui ne sont pas réguliers, et encore de la façon dont ils sont définis, il est clair qu'un modèle peut être adapté à eux. Un tel langage est (a ^ n) (b ^ n). Il est clair que cela est un modèle, et pourtant ce n'est pas une langue régulière. Alors maintenant, je me demande ce qui est à gauche il des langues régulières qui les rend régulièrement, et cette langue non?

Answer 1

L'étymologie du nom vient du travail des années 1950 Kleene décrivant ensembles réguliers en utilisant sa notation mathématique créée à cet effet. Voir cette .

Answer 2

Intuitivement expliquer la science informatique est ... difficile. Je vais donner un coup de feu, mais gardez à l'esprit que certains de cela va être « assez proche », mais pas en théorie rigoureuse.

Une langue régulière est celui qui peut être décidé par une machine qui est équivalent à un calcul des automates finis (DFA / NDFA). Un automate fini peut être considéré comme une machine qui fonctionne uniquement dans les Etats, pas de stockage. Ainsi, vous pouvez voir que ⁿ b ⁿ ne peut pas être régulier car il nécessite une machine qui peut compter le nombre d'un et des b (et doit donc avoir infinie * capacité de stockage) afin de les comparer.

A titre de comparaison, (abc) ⁿ est régulière, car le nombre de répétitions est hors de propos.

Pour une plus rigoureuse (et vue en conséquence plus dense) vérifier la wikipedia article et pages liées .

_{* L'infini n'a pas d'importance ici, mais je le mentionne pour être complet. Il pourrait être plus facile de penser que le stockage « heureusement, toujours juste assez ».}

Answer 3

Peut-être l'article de Wikipedia sur langues régulières peuvent expliquer mieux que nous pouvons. Cependant, je vais donner un coup de feu.

Du point de vue théorique, une langue régulière (ensemble de cordes) est celui qui peut être généré à l'aide d'un automate à états finis . En termes de programmeur, cela équivaut à dire qu'il peut être généré en utilisant expressions régulières . Ainsi, toutes les langues finies (ensembles de cordes) sont régulières, mais il y a certaines langues infinies, comme un ⁿ b ⁿ (la langue de toutes les chaînes de na de suivi de n b) pour qui ne peuvent pas être reconnus au moyen d'un FSA ou des expressions régulières. Il existe des dispositifs informatiques plus puissants (comme les ordinateurs modernes, qui sont modélisés en utilisant ) Machines de Turing qui peut reconnaître ces langues.

La raison des expressions régulières sont utilisées tant dans la programmation pour la recherche de chaîne est qu'ils peuvent reconnaître la grande majorité des chaînes qui nous sont importants pour les programmeurs, et en même temps peut être mis en œuvre pour rechercher très rapidement en utilisant des automates à états finis.

Answer 4

Le mot regular dans regular expression se réfère au concept mathématique de régulier, pas le concept anglais. Tout comme la façon dont le mot prime en mathématiques peu de rapport avec Premier boeuf.

Il est hérité par CS (qui est une branche des mathématiques) de se référer à un concept plus spécifique: http : //en.wikipedia.org/wiki/Regular_language

Answer 5

expression régulière ne sont pas vraiment régulière, le nom est étymologique.