Langue régulière - Regular language

En informatique théorique et en théorie des langages formels , un langage régulier (appelé aussi langage rationnel ) est un langage formel qui peut être défini par une expression régulière , au sens strict en informatique théorique (par opposition à de nombreux moteurs d'expressions régulières modernes, qui sont complétées par des fonctionnalités permettant la reconnaissance des langues non régulières).

Alternativement, un langage régulier peut être défini comme un langage reconnu par un automate fini . L'équivalence des expressions régulières et des automates finis est connue sous le nom de théorème de Kleene (d'après le mathématicien américain Stephen Cole Kleene ). Dans la hiérarchie de Chomsky , les langages réguliers sont les langages générés par les grammaires de Type-3 .

Définition formelle

L'ensemble des langages réguliers sur un alphabet est défini récursivement comme suit :

  • Le langage vide Ø est un langage régulier.
  • Pour chaque a ∈ Σ ( a appartient à Σ), le langage singleton { a } est un langage régulier.
  • Si A est un langage régulier, A * ( Kleene star ) est un langage régulier. Pour cette raison, la langue de chaîne vide {ε} est également régulière.
  • Si A et B sont des langues régulières, alors AB (union) et AB (concaténation) sont des langues régulières.
  • Aucune autre langue supérieure à Σ n'est régulière.

Voir expression régulière pour la syntaxe et la sémantique des expressions régulières.

Exemples

Tous les langages finis sont réguliers ; en particulier la chaîne vide language {ε} = Ø* est régulière. D'autres exemples typiques incluent le langage composé de toutes les chaînes de l'alphabet { a , b } qui contiennent un nombre pair de a s, ou le langage composé de toutes les chaînes de la forme : plusieurs a s suivi de plusieurs b s.

Un exemple simple de langage qui n'est pas régulier est l'ensemble de chaînes { a n b n | n 0 }. Intuitivement, il ne peut pas être reconnu avec un automate fini, car un automate fini a une mémoire finie et il ne peut pas se souvenir du nombre exact de a. Des techniques pour prouver ce fait rigoureusement sont données ci - dessous .

Formalismes équivalents

Un langage régulier satisfait les propriétés équivalentes suivantes :

  1. c'est le langage d'une expression régulière (selon la définition ci-dessus)
  2. c'est le langage accepté par un automate fini non déterministe (NFA)
  3. c'est le langage accepté par un automate fini déterministe (DFA)
  4. il peut être généré par une grammaire régulière
  5. c'est le langage accepté par un automate fini alterné
  6. c'est le langage accepté par un automate fini bidirectionnel
  7. il peut être généré par une grammaire de préfixe
  8. il peut être accepté par une machine de Turing en lecture seule
  9. il peut être défini en logique monadique du second ordre ( théorème de Büchi-Elgot-Trakhtenbrot )
  10. il est reconnu par un monoïde syntaxique fini M , ce qui signifie que c'est la préimage { w ∈ Σ * | f ( w ) ∈ S } d'un sous-ensemble S d'un monoïde fini M sous un homomorphisme de monoïde f : Σ *M du monoïde libre sur son alphabet
  11. le nombre de classes d'équivalence de sa congruence syntaxique est fini. (Ce nombre est égal au nombre d'états de l' automate fini déterministe minimal acceptant L .)

Les propriétés 10. et 11. sont des approches purement algébriques pour définir les langages réguliers ; un ensemble similaire d'énoncés peut être formulé pour un monoïde M Σ * . Dans ce cas, l'équivalence sur M conduit au concept de langage reconnaissable.

Certains auteurs utilisent l'une des propriétés ci-dessus différentes de "1". comme définition alternative des langages réguliers.

Certaines des équivalences ci-dessus, en particulier celles parmi les quatre premiers formalismes, sont appelées théorème de Kleene dans les manuels. Précisément lequel (ou quel sous-ensemble) est appelé tel varie selon les auteurs. Un manuel appelle l'équivalence des expressions régulières et des NFA ("1." et "2." ci-dessus) "théorème de Kleene". Un autre manuel appelle l'équivalence des expressions régulières et des DFA ("1." et "3." ci-dessus) "théorème de Kleene". Deux autres manuels prouvent d'abord l'équivalence expressive des NFA et des DFA (« 2 » et « 3. »), puis énoncent le « théorème de Kleene » comme l'équivalence entre les expressions régulières et les automates finis (ce dernier dit décrire des « langues reconnaissables »). . Un texte à orientation linguistique assimile d'abord les grammaires régulières ("4." ci-dessus) aux DFA et NFA, appelle les langues générées par (l'un de) ces "réguliers", après quoi il introduit des expressions régulières qu'il appelle pour décrire des "langues rationnelles", et enfin énonce le "théorème de Kleene" comme la coïncidence des langages réguliers et rationnels. D'autres auteurs définissent simplement « expression rationnelle » et « expressions régulières » comme synonymes et font de même avec les « langues rationnelles » et les « langues régulières ».

Apparemment, le terme « régulier » provient d'un rapport technique de 1951 où Kleene a introduit des « événements réguliers » et a explicitement accueilli « toute suggestion quant à un terme plus descriptif » . Noam Chomsky , dans son 1959 article fondateur, a utilisé le terme « régulier » dans un sens différent au premier ( en référence à ce qu'on appelle « forme normale de Chomsky » aujourd'hui), mais on a remarqué que ses « langues d'état fini » étaient équivalents à de Kleene « régulière événements" .

Propriétés de fermeture

Les langages réguliers sont fermés sous diverses opérations, c'est-à-dire que si les langages K et L sont réguliers, il en est de même du résultat des opérations suivantes :

Propriétés de décidabilité

Étant donnés deux automates finis déterministes A et B , il est possible de décider s'ils acceptent le même langage. En conséquence, en utilisant les propriétés de fermeture ci - dessus , les problèmes suivants sont également décidables pour des automates finis déterministes arbitrairement donnés A et B , avec les langages acceptés L A et L B , respectivement :

  • Confinement: est L A de L B  ?
  • Disjoints: est L AL B = {}?
  • Vide : est-ce que L A = {} ?
  • Universalité : est-ce que L A = Σ *  ?
  • Adhésion : étant donné un ∈ Σ * , est-ce qu'unL B  ?

Pour les expressions régulières, le problème d'universalité est déjà NP-complet pour un alphabet singleton. Pour les alphabets plus grands, ce problème est PSPACE-complet . Si les expressions régulières sont étendues pour permettre également un opérateur carré , avec " A 2 " dénotant la même chose que " AA ", encore seuls les langages réguliers peuvent être décrits, mais le problème d'universalité a une borne inférieure d'espace exponentiel, et est en fait complet pour espace exponentiel par rapport à la réduction en temps polynomial.

Résultats de complexité

Dans la théorie de complexité , la classe de complexité de toutes les langues régulières est parfois appelée REGULIER ou REG et est égal à DSPACE (O (1)), les problèmes de décision qui peuvent être résolus dans l' espace constant (l'espace utilisé est indépendant de la taille d'entrée ). REGULARAC 0 , car il (trivialement) contient le problème de parité de déterminer si le nombre de bits à 1 dans l'entrée est pair ou impair, ce problème n'a pas de AC 0 . En revanche, REGULAR ne contient pas AC 0 , car la langue non régulière des palindromes , ou la langue non régulière peuvent toutes deux être reconnues dans AC 0 .

Si un langage n'est pas régulier, il nécessite une machine avec au moins Ω (log log n ) d'espace à reconnaître (où n est la taille d'entrée). En d'autres termes, DSPACE( o (log log n )) est égal à la classe des langages réguliers. En pratique, la plupart des problèmes non réguliers sont résolus par des machines prenant au moins un espace logarithmique .

Emplacement dans la hiérarchie de Chomsky

Langage régulier dans les classes de la hiérarchie de Chomsky.

Pour situer les langages réguliers dans la hiérarchie de Chomsky , on remarque que chaque langage régulier est hors contexte . L'inverse n'est pas vrai : par exemple, le langage composé de toutes les chaînes ayant le même nombre de a que de b est sans contexte mais pas régulier. Pour prouver qu'un langage n'est pas régulier, on utilise souvent le théorème de Myhill-Nerode et le lemme de pompage . D'autres approches incluent l'utilisation des propriétés de fermeture des langages réguliers ou la quantification de la complexité de Kolmogorov .

Les sous-classes importantes de langages réguliers comprennent

  • Langues finies, celles qui ne contiennent qu'un nombre fini de mots. Ce sont des langues régulières, car on peut créer une expression régulière qui est l' union de chaque mot de la langue.
  • Langages sans étoile , ceux qui peuvent être décrits par une expression régulière construite à partir du symbole vide, des lettres, de la concaténation et de tous les opérateurs booléens (voir algèbre des ensembles ) y compris la complémentation mais pas l' étoile de Kleene : cette classe comprend tous les langages finis.

Le nombre de mots dans une langue régulière

Soit le nombre de mots de longueur dans . La fonction génératrice ordinaire de L est la série formelle formelle

La fonction génératrice d'un langage L est une fonction rationnelle si L est régulier. Donc pour tout langage régulier la suite est constante-récursive ; c'est-à-dire qu'il existe une constante entière , des constantes complexes et des polynômes complexes tels que pour chaque le nombre de mots de longueur dans est .

Ainsi, la non-régularité de certaines langues peut être prouvée en comptant les mots d'une longueur donnée dans . Considérons, par exemple, le langage Dyck des chaînes de parenthèses équilibrées. Le nombre de mots de longueur dans la langue dyck est égal au nombre catalan , qui n'est pas de la forme , témoignant de la non-régularité de la langue dyck. Des précautions doivent être prises car certaines des valeurs propres pourraient avoir la même amplitude. Par exemple, le nombre de mots de longueur dans la langue de tous les mots binaires pairs n'est pas de la forme , mais le nombre de mots de longueur paire ou impaire sont de cette forme ; les valeurs propres correspondantes sont . En général, pour tout langage régulier, il existe une constante telle que pour tout , le nombre de mots de longueur est asymptotiquement .

La fonction zêta d'un langage L est

La fonction zêta d'un langage régulier n'est pas en général rationnelle, mais celle d'un langage cyclique arbitraire l' est.

Généralisations

La notion de langage régulier a été généralisée aux mots infinis (voir ω-automates ) et aux arbres (voir automate d'arbres ).

L'ensemble rationnel généralise la notion (de langage régulier/rationnel) aux monoïdes qui ne sont pas nécessairement libres . De même, la notion de langage reconnaissable (par un automate fini) a un homonyme comme ensemble reconnaissable sur un monoïde qui n'est pas nécessairement libre. Howard Straubing note à propos de ces faits que « le terme « langue courante » est un peu malheureux. Les articles influencés par la monographie d' Eilenberg utilisent souvent le terme « langage reconnaissable », qui fait référence au comportement des automates, ou « langage rationnel », qui fait référence à des analogies importantes entre les expressions régulières et les séries de puissances rationnelles. (En fait, Eilenberg définit des sous-ensembles rationnels et reconnaissables de monoïdes arbitraires ; les deux notions ne coïncident généralement pas.) Cette terminologie, bien que mieux motivée, n'a jamais vraiment fait son chemin, et le « langage courant » est utilisé presque universellement.

La série rationnelle est une autre généralisation, cette fois dans le contexte d'une série de puissance formelle sur un semi-anneau . Cette approche donne lieu à des expressions rationnelles pondérées et à des automates pondérés . Dans ce contexte algébrique, les langages réguliers (correspondant aux expressions rationnelles à pondération booléenne ) sont généralement appelés langages rationnels . Toujours dans ce contexte, le théorème de Kleene trouve une généralisation appelée théorème de Kleene-Schützenberger .

Apprendre à partir d'exemples

Remarques

Les références

Lectures complémentaires

  • Kleene, SC : Représentation des événements dans les réseaux nerveux et les automates finis. Dans : Shannon, CE, McCarthy, J. (eds.) Automata Studies, pp. 3-41. Princeton University Press, Princeton (1956); il s'agit d'une version légèrement modifiée de son rapport de 1951 de la RAND Corporation du même titre, RM704 .
  • Sakarovitch, J (1987). « Le théorème de Kleene revisité ». Tendances, techniques et problèmes en informatique théorique . Notes de cours en informatique. 1987 . p. 39-50. doi : 10.1007/3540185356_29 . ISBN 978-3-540-18535-2.

Liens externes