Cours : Qu'est ce qu'un mot

Description

-1- -2-PlanINF 421 — 08 Luc Maranget◮ Qu’est-ce qu’un mot ?◮ Comment d´ecrire des ensembles simples de mots ?◮ Programmation de tout c¸a.` `A quoi c¸a sert ? A jouer aux mots-crois´es (entre autres) ! MaisExpressions r´eguli`eresaussi :(rationnelles)`◮ A d´efinir des notations, telles que l’´ecriture des int dans unsource Java.`◮ A effectuer des recherches et des modifications dans du texte.`◮ A nettoyer votre r´[e-mail]◮ Donne un bon exemple de la distinction syntaxe/s´emantique.http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/-3- -4-Jeux avec les mots La r´ep´etitionPour se donner plus de libert´e, on introduit *Soient A et B deux humains, A joue aux mots crois´es, B l’aide :◮ .* : tous les mots (r´ep´etition de .).◮ A pose une question : il ne manque pas d’air, en sept lettres laseconde est x, l’avant-derni`ere est n ? oxyg`ene ⊲ Les mots qui contiennent (au moins) deux k : .*k.*k.*◮ Une autre : livre sacr´e en cinq lettres, commence par b ou c ? ◮ Si p motif, alors p* : r´ep´etition du motif.bible ou coran.⊲ Les mots dont les lettres sont prises dans abcd :(a|b|c|d)*.Dans les questions de A, il y a une partie typiquement humaine, et⊲ Lettres prises dans abcd et efghune autre plus simple.alternativement :((a|b|c|d)(e|f|g|h))*.Si B est un ordinateur, on peut donner des motifs...Essayez pour voir :◮ .x...n. (( . ) est une lettre quelconque).# egrep -x ’.*k.*k.*’ /usr/share/dict ...

Informations

• Publié par: Mafor
• Nombre de lectures: 39
• Langue: Français

Extrait

-1-

-3-

INF 421 — 08

Luc Maranget

Expressionsr´eguli`eres (rationnelles)

[e-mail] http://www.enseignement.polytechnique.fr/profs/ informatique/Luc.Maranget/421/

Jeux avec les mots Soient A et B deux humains, A joueauxmotscroise´s, B l’aide : ◮ A pose une question : il ne manque pas d’air, en sept lettres la seconde est x ,l’avant-derni`ereest n ? oxyge`ne ◮ Uneautre:livresacr´eencinqlettres,commencepar b ou c ? bible ou coran . Dans les questions de A , il y a une partie typiquement humaine, et une autre plus simple. Si B est un ordinateur, on peut donner des motifs . . . ◮ .x...n. ( ✭ . ✮ est une lettre quelconque). ◮ (b|c).... ( ✭ | ✮ est l’alternative). Si on dispose d’un fichiers de mots, on peut extraire les mots qui conviennent par egrep , par exemple egrep -x ’.x...n. file ’

-2-

-4-

Plan ◮ Qu’est-ce qu’un mot ? ◮ Commentde´criredesensemblessimplesdemots? ◮ Programmationdetoutc¸a. ` ` Aquoic¸asert?Ajouerauxmots-croise´s(entreautres)!Mais aussi : ` ◮ Ade´finirdesnotations,tellesquel’e´crituredes int dans un source Java. ` ◮ A effectuer des recherches et des modifications dans du texte. ` ◮ Anettoyervotrere´pertoire. ◮ Donneunbonexempledeladistinctionsyntaxe/s´emantique.

Lar´ep´etition Poursedonnerplusdelibert´e,onintroduit * ◮ .* :touslesmots(r´epe´titionde . ). ⊲ Les mots qui contiennent (au moins) deux k : .*k.*k.* ◮ Si p motif, alors p * :r´epe´titiondumotif. ⊲ Les mots dont les lettres sont prises dans abcd : (a|b|c|d)* . ⊲ Lettres prises dans abcd et efgh alternativement : ((a|b|c|d)(e|f|g|h))* . Essayez pour voir : # egrep -x ’.*k.*k.*’ /usr/share/dict/french bookmaker bookmakers ...

-5-

-7-

Les mots ◮ Soit Σ un alphabet (ensembledecaracte`res). ◮ Les mots (ensemble Σ ∗ )sontlessuitesfiniesdecaracte`res. ◮ Un langage est un sous-ensemble de Σ ∗ . ⊲ Langage des mots francais. ¸ ⋆ Σ = { a  b  . . . } (alphabet usuel, avec accents). ⋆ D´efinipar,ledictionnaire(del’Acade´mie,sionytient). ⊲ Langagedese´crituresenbase10. ⋆ Σ = { 0  1  . . .  9 } (chiffres). ⋆ De´finiparunep´eriphrasegenre ✭ le chiffre 0 , ou une suite non-vide de chiffres qui ne commence pas par 0 ✮ .

Les mots sont des chaˆınes La classe String a ,dupackage(importe´pard´efaut) java.lang . ◮ Mot vide : "" . ◮ Pourre´cup´ererlecaracte`red’indice k . public char charAt ( int index ) ◮ Concat´enerdeuxchaines: String t = m0 + m1 ; Oume´thode concat . String t = m0 . concat ( m1 ) ; ◮ De´composerenpr´efixeetsuffixe,aveclam´ethode substring . String pref = m . substring (0, k ) // m [0    k [ String suff = m . substring ( k ) // m [ k    n [ a http://java.sun.com/j2se/1.5.0/docs/api/java/lang/String.html

-6-

-8-

O ´ ations sur les mots per Un mot est par exemple m = a 0 a 1    a n − 1 ( n longueur de m ). ◮ R´ecup´ererlecaracte`red’indice k : a k . ◮ Concat´enerdeuxmots:lesmettrel’underri`erel’autre. ′ ′ ′ ′ m  m = a 0 a 1    a n − 1 a 0 a 1    a n ′ − 1 ⊲ Operation associative. ´ ⊲ Motvide´ele´mentneutrea`gaucheeta`droite ( ǫ  m = m  ǫ = m ). ⊲ Dans t = m  m ′ , m est un pr´efixe de t , m ′ est un suffixe de t . ◮ Notationabre´g´ee: t = mm ′ . ◮ Notation des sous-mots : m [ i    j [= a i a i +1    a j − 1

Op´erationssurleslangages ◮ Union ensembliste. ◮ Concat´enation L 1  L 2 = { m 1  m 2 | m 1 ∈ L 1 ∧ m 2 ∈ L 2 } ◮ Ite´ration. L 0 = { ǫ } L n +1 = L n  L L ⋆ = [ L i i ∈ N Autrement dit : m ∈ L ⋆ ⇐⇒ m = m 1  m 2    m n  avec m i ∈ L

9--

-11-

Lesexpressionsre´gulie`res Unerepre´sentation p d’un langage L . ◮ Le mot vide ´ te { ǫ } . ǫ represen ◮ Le caract`ere c repre´sente { c } . ◮ L’alternative p 1 | p 2 represente L 1 ∪ L 2 . ◮ Laconcat´enation p 1  p 2 repr´esente L 1  L 2 . ◮ Lar´epe´tition p * repr´esente L ⋆ . Pourl’informaticien,lad´efinitionme´riteunede´compositionen syntaxe et s´emantique .

Exemple de motif |   a * b * b a Enpratiqueone´crit(syntaxeconcre`te) ( a  ( b* )) | ( b  ( a* )) ou plus simplement ab*|ba*

1--0

-12-

Syntaxedesexpressionsr´egulie`res Un motif p est defini ainsi. ´ ◮ Le mot vide ǫ est un motif. ◮ Uncaracte`re c est un motif. ◮ Si p 1 et p 2 sont des motifs, alors. . . ⊲ L’alternative p 1 | p 2 est un motif. ⊲ Laconcat´enation p 1  p 2 est un motif. ◮ Si p est un motif, alors. . . ⊲ La´epe´tition p * est un motif. r Important C’estuned´efinitiondestructured’arbre,sansplusde pre´cisions. P = { ǫ } ⊎ Σ ⊎ ( P × { |   } × P ) ⊎ ( P × { * } )

Priorite´sdesop´erateurs C’estcommepourlesexpressionsarithm´etiques.Parordre croissantdepriorit´e. ◮ L’alternative ✭ | ✮ (comme l’addition). ◮ Laconcate´nation ✭  ✮ (commelamultiplication,peuteˆtre omis). ◮ La r´ep´etition ✭ * ✮ (postfixe,commelamise`alapuissance). Donc ◮ ab* se comprend comme a(b*) . ◮ ab|c se comprend comme (ab)|c . ◮ ab*|c se comprend comme (a(b*))|c .

1--3

-15-

Encore plus precis ´ ◮ ab* se comprend comme a(b*) .  a * b ◮ ab|c se comprend comme (ab)|c . |  c a b ◮ ab*|c se comprend comme (a(b*))|c . |  c a * b

Se´mantiquedesexpressionsr´egulieres ` La fonction [[  ]],de´finiedesmotifsdanslesensemblesdemots, associeunevaleur`achaquemotif. [[ ǫ ]]= { ǫ } [[ c ]]= { c } [[ p 1 | p 2 ]]=[[ p 1 ]] ∪ [[ p 2 ]] [[ p 1  p 2 ]]=[[ p 1 ]]  [[ p 2 ]] [[ p * ]]=[[ p ]] ∗

Inversement, Un langage L est dit re´gulier quand il existe un motif p tel que [[ p ]]= L .

-14-

-16-

Lespriorit´esnere´solventpastout Comment comprendre abc , comme a(bc) ou (ab)c ?

  a   c b c a b Celan’aaufinalpasd’importance,enraisondel’associativite´de laconcate´nation. Mais il y a bien deux arbres possibles. Undernierd´etail:onpeutrepre´senterlemotifvidepar () .

Exemplesdelangagesre´guliers ◮ Lesmotsfran¸cais. Grossealternativedesmotsdudictionnaire(del’Acade´mie) ◮ Toutlangagefiniestr´egulier(meˆmeprincipe). ´ ◮ Ecritured´ecimaledesentiers. 0|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* ◮ Motsconstitu´esde 0 et de 1 alterne´s ⊲ Commence par 0 , finit par 1 : (01)* (ou vide). ⊲ Commence par 0 , finit par 0 : (01)*0 . ⊲ etc. (01)*|(01)*0|(10)*|(10)*1

1--7

-19-

Ou mieux (|1)(01)*(|0) Motsconstitue´sde 0 et 1 altern´es. ◮ Commence par 0 , finit par 1 : (01)* (ou vide). ◮ Commence par 0 , finit par 0 : (01)*0 . ◮ Commence par 1 , finit par 1 : 1(01)* . ◮ Commence par 1 , finit par 0 : 1(01)*0 . Soit (01)*|(01)*0|1(01)*|1(01)*0 . ( L  L 1 ) ∪ ( L  L 2 ) = L  ( L 1 ∪ L 2 ) L  { ǫ } = L Soit ((01)*|(|0))|(1(01)*(|0)) . ( L 1  L ) ∪ ( L 2  L ) = ( L 1 ∪ L 2 )  L { ǫ }  L = L Soit (|1)(01)*(|0) .

Arbredede´rivation Un tel arbre donne une preuve, par exemple de ab*|ba*  baa . a  a a*  ǫ a  a a*  a b  b a* ≺ aa ba*  baa ab*|ba*  baa

C’estunpremieremploidelad´efinitionformelledufiltrage. Autresemplois(desre`glesd’inf´erence). ◮ Impl´ementation(na¨ıve)dufiltrage. ◮ Preuvesparinductionssousl’hypoth`ese p  m .

-18-

-20-

Filtrage Si m ∈ [[ p ]], on dit que p filtre m ,note´ p  m . De´finitionformelleparaxiomesetr`eglesd’inf´erences. Se Empty Char p 1 q  m 1 p 2  m 2 ǫ  ǫ c  c p 1 p 2  m 1 m 2

OrLeft OrRight p 1  m p 2  m p 1 | p 2  m p 1 | p 2  m

S StarSeq tarEmpty p  m 1 p *  m 2 p *  ǫ p *  m 1 m 2

Notationssupple´mentaires Exprimablesaveclesconstructionsdebase,ellen’´etendentpasla classedeslangagesr´eguliers. ◮ Le joker ✭ . ✮ ,[[ . ]] = Σ. Σ = { a 0  . . . a n − 1 } fini, exprimable comme a 0 |    | a n − 1 . ◮ L’ option p ? ,de´finiecomme p | () . ◮ La r´ep´etitonaumoinsunefois p + , d´efinie comme pp * . ◮ Lesensemblesdecaracte`res,e´critsentrecrochets [    ] . Par exemple [aeiou] , ou [0-9] (suppose un ordre sur les caract`eres). ◮ Lescomple´mentaires,´ecrits [^    ] . Par exemple [^a-zA-Z0-9] (caract`eresnonalphanum´eriques).