Morphèmes, morphologie
Expressions régulières
Les automates finis ont été très étudiés par Chomsky et les pionniers de l'informatique théorique, à partir des années 60, et un très grand nombre de leurs propriétés formelles ont alors été explicitées. Nous n'évoquerons ici que quelques-unes d'entre elles, sans rentrer dans les détails techniques et sans fournir aucune démonstration.
Les automates finis reconnaissent (ou engendrent, suivant le point de vue adopté) une classe de langages particulière appelée langages réguliers ou langages rationnels. Un langage est régulier (ou rationnel) s'il existe un automate qui reconnaît exactement ce langage. On peut aussi caractériser cette famille de langages par d'autres moyens. Nous verrons plus loin une caractérisation en termes de grammaires formelles. Ici, nous présentons la caractérisation par les expressions régulières.
Une expression régulière est une suite de symboles prise parmi :
un vocabulaire fini V
le symbole qui représente la "chaîne vide"
les symboles : "|" et ".", ainsi que les parenthèses "(" et ")"
les symboles "+" et "*" utilisés en exposants
Elle doit être de plus bâtie en respectant les règles de construction suivantes :
tout élément de V∪{} est une expression régulière ;
si U est une expression régulière, alors (U) est aussi une expression régulière : les parenthèses sont utilisées comme en mathématiques, pour délimiter des sous-parties d'expressions régulières ;
si U et T sont toutes les deux des expressions régulières, alors U|T et U.T (souvent réduite à UT) sont des expressions régulières : U|T=U∪ T={w|w∈ U ou w∈ T} représente le choix entre un élément de U et un élément de T, tandis que UT={ut|u∈ U et t∈ T} représente l'ensemble des concaténations d'un élément de U et d'un élément de T ;
si U est une expression régulière, alors U+ et U* sont des expressions régulières : U+={u1u2...un|∀ i, ui∈ U} représente l'ensemble des concaténations un nombre quelconque de fois (au moins une) d'éléments de U, et U*=U+∪{} est la même concaténation, y compris 0 fois (ce qui donne la chaîne vide).
Le symbole joue le rôle d'élément neutre pour la concaténation : pour tout symbole w∈ V, w.=.w=w. A titre d'exemple, l'automate de la figure 4.4 construit sur le vocabulaire V={a,b} reconnaît le langage constitué d'un nombre quelconque (éventuellement nul) de symboles a suivi d'un nombre quelconque mais non nul de symboles b (parce que tout chemin, pour passer de l'état initial 1 à l'état final 2, doit obligatoirement emprunter la transition étiquetée par b entre ces deux états). Il peut être représenté par l'expression régulière : a*b+.
Figure 4.4 : un automate fini dont le langage est a*b+
Le langage a*b+ est un langage infini, puisqu'il contient un nombre non borné de mots différents : a*b+={b, ab, bb, aab, abb, bbb, ...}. On voit que la puissance des automates finis et des expressions régulières vient de ce qu'ils permettent de caractériser un nombre infini de mots différents à l'aide d'un nombre fini d'éléments. Néanmoins, si les langues naturelles contiennent un nombre infini d'unités lexicales, c'est grâce au fait que les morphèmes lexicaux constituent une liste ouverte (et qu'on peut toujours inventer de nouveaux mots) et non grâce à l'expressivité des affixations, telles qu'on peut les exprimer dans des automates finis.
Tout langage régulier peut être exprimé sous la forme d'une (ou plusieurs) expression(s) régulière(s) (et inversement). Passer d'un automate à une expression régulière ou inversement n'est pas toujours simple. Le langage (fini) reconnu par l'automate morphologique précédent, en figure 4.3, peut être représenté par exemple par l'expression régulière complexe suivante :
(in|).(imit|analys|désir|nomm).((é.(|e|s|es))|able(|s))
Yüklə 83,85 Kb. Dostları ilə paylaş: 
|