Word (matematikk)

I matematikk eller teoretisk datamaskin er et ord et resultat endelige elementer tatt i et sett . Det hele kalles alfabetet , dets deler kalles symboler eller bokstaver . De sier det er et trygt ord . w{\ displaystyle w}PÅ{\ displaystyle A}PÅ{\ displaystyle A}w{\ displaystyle w} PÅ{\ displaystyle A}

Eksempler

• Et "binært ord". Det er et ord på et alfabet med to symboler, generelt bemerket og . For eksempel er den binære utviklingen av et naturlig tall, eller dets binære skrift, sekvensen av sifrene til dens representasjon i basen . Så, den binære skrivingen av "nitten" er .0{\ displaystyle 0}1{\ displaystyle 1}2{\ displaystyle 2}10011{\ displaystyle 10011}
• En " deoksyribonukleinsyresekvens  " (DNA). Det er et ord som vanligvis dannes av en serie på fire bokstaver som tilsvarer de fire nukleotidene som danner DNA-kjeden: A for "adenin", G for "guanin", T for "tymin", C for "cytosin".
• Et "  protein  " er et makromolekyl som består av en kjede av aminosyrer . Det er 20 aminosyrer. Det er derfor et ord på et alfabet med 20 symboler.

Eiendommer

Ett ord skrives enklere:w=(på1,på2,...,påikke){\ displaystyle w = (a_ {1}, a_ {2}, \ ldots, a_ {n})}w=på1på2⋯påikke{\ displaystyle w = a_ {1} a_ {2} \ cdots a_ {n}}

Den lengde av et ord er antallet posisjoner av de symboler som utgjør det: den ovennevnte ord er lengden . For eksempel er ordet på alfabetet lengde 7. Et ord kan være tomt. Det er ordet lengde 0. Det blir ofte notert ε. w{\ displaystyle w}ikke{\ displaystyle n}påbpåvs.påbpå{\ displaystyle abacaba}PÅ={på,b,vs.}{\ displaystyle A = \ {a, b, c \}}

Den sammenkobling av to ord og er ordet oppnådd ved å sette ende mot ende og . For eksempel sammenkobling av og gir . Sammenkobling er en assosiativ operasjon, men ikke en kommutativ. Dens nøytrale element er ordet tomt. u{\ displaystyle u}v{\ displaystyle v}uv{\ displaystyle uv}u{\ displaystyle u}v{\ displaystyle v}u=påbrpåvs.på{\ displaystyle u = abraca}v=dpåbrpå{\ displaystyle v = dabra}uv=påbrpåvs.pådpåbrpå{\ displaystyle uv = abracadabra}

Ordsettet på et alfabet , utstyrt med sammenkoblingen, danner derfor en monoid . Som en algebraisk struktur er den en fri monoid i betydningen universell algebra . Dette betyr at ethvert ord er et produkt av sammenkobling av symbolene som komponerer det. PÅ{\ displaystyle A}

Ordsettet på et alfabet er tradisjonelt notert . PÅ{\ displaystyle A}PÅ∗{\ displaystyle A ^ {*}}

Ytterligere terminologi

• De prefikser av et ord er ord iU ^ og , for . De 5 prefikser av ordet er: ε, , , og seg selv. Hvis vi ekskluderer det tomme ordet, snakker vi om et ikke-tomt prefiks , hvis vi ekskluderer selve ordet, snakker vi om et riktig prefiks . Tilsvarende er et ord et prefiks av et ord hvis det er et ord som .w=på1⋯påikke{\ displaystyle w = a_ {1} \ cdots a_ {n}}ikke+1{\ displaystyle n + 1}på1⋯påJeg{\ displaystyle a_ {1} \ cdots a_ {i}}Jeg=1,...,ikke{\ displaystyle i = 1, \ ldots, n}
  påbpåvs.{\ displaystyle abac}på{\ displaystyle a}påb{\ displaystyle ab}påbpå{\ displaystyle aba}påbpåvs.{\ displaystyle abac}s{\ displaystyle p}w{\ displaystyle w}s{\ displaystyle s}w=ss{\ displaystyle w = ps}

• De suffikser av et ord er ord iU ^ og , for . Den fem suffiks av ordet er: ord , , , og ε. Tilsvarende er et ord et suffiks av et ord hvis det er et ord som .w=på1⋯påikke{\ displaystyle w = a_ {1} \ cdots a_ {n}}ikke+1{\ displaystyle n + 1}påJeg⋯påikke{\ displaystyle a_ {i} \ cdots a_ {n}}Jeg=1,...,ikke{\ displaystyle i = 1, \ ldots, n}
  påbpåvs.{\ displaystyle abac}påbpåvs.{\ displaystyle abac}bpåvs.{\ displaystyle bac}påvs.{\ displaystyle ac}vs.{\ displaystyle c}s{\ displaystyle s}w{\ displaystyle w}s{\ displaystyle p}w=ss{\ displaystyle w = ps}

• De faktorene av et ord er ordene , for . De faktorer av ordet er det ord ε, , , , , , , , og . Tilsvarende er et ord en faktor av et ord hvis det er ord som .w=på1⋯påikke{\ displaystyle w = a_ {1} \ cdots a_ {n}}påJeg⋯påj{\ displaystyle a_ {i} \ cdots a_ {j}}1≤Jeg≤j≤ikke{\ displaystyle 1 \ leq i \ leq j \ leq n}
  påbpåvs.{\ displaystyle abac}på{\ displaystyle a}b{\ displaystyle b}vs.{\ displaystyle c}påb{\ displaystyle ab}bpå{\ displaystyle ba}påvs.{\ displaystyle ac}påbpå{\ displaystyle aba}bpåvs.{\ displaystyle bac}påbpåvs.{\ displaystyle abac}x{\ displaystyle x}w{\ displaystyle w}s,s{\ displaystyle p, s}w=sxs{\ displaystyle w = pxs}

• Et ord er et stikkord til et ord hvis det er en faktorisering i ord som . Dermed oppnås ved å slette symboler i . For eksempel er underordet til .x{\ displaystyle x}y{\ displaystyle y}y=z0x1z1x2⋯xikkezikke{\ displaystyle y = z_ {0} x_ {1} z_ {1} x_ {2} \ cdots x_ {n} z_ {n}}z0,x1,z1,x2,...,xikke,zikke{\ displaystyle z_ {0}, x_ {1}, z_ {1}, x_ {2}, \ ldots, x_ {n}, z_ {n}}x=x1x2⋯xikke{\ displaystyle x = x_ {1} x_ {2} \ cdots x_ {n}}
  x{\ displaystyle x}y{\ displaystyle y}y{\ displaystyle y}påpå{\ displaystyle aa}påbpåvs.{\ displaystyle abac}

• Den speilbilde eller retur av et ord er ordet . For eksempel er ordets speilbilde .w=på1⋯påikke{\ displaystyle w = a_ {1} \ cdots a_ {n}}w~=påikke⋯på1{\ displaystyle {\ tilde {w}} = a_ {n} \ cdots a_ {1}}
  påbpåvs.{\ displaystyle abac}vs.påbpå{\ displaystyle caba}

• En palindrom er et ord som er lik speilbildet.
  For eksempel er ordet et palindrom.påbpåvs.påbpå{\ displaystyle abacaba}

• Et ord er et heltall av et ord hvis det er et positivt heltall som ( gjentatte ganger).x{\ displaystyle x}y{\ displaystyle y}ikke{\ displaystyle n}x=yikke{\ displaystyle x = y ^ {n}}y{\ displaystyle y}ikke{\ displaystyle n}

• Et ord er primitivt hvis det ikke er hele kraften til et annet ord.
  For eksempel er ordet ikke primitivt, fordi det er kvadratet av ordet .boikkeboikke{\ displaystyle bonbon}boikke{\ displaystyle bra}

• To ord og er konjugert hvis det er ord og slik som og . For eksempel ordene og er konjugert. Konjugasjon er en ekvivalensrelasjon .x{\ displaystyle x}y{\ displaystyle y}s{\ displaystyle p}s{\ displaystyle s}x=ss{\ displaystyle x = ps}y=ss{\ displaystyle y = sp}
  påbpåpåb{\ displaystyle abaab}påbpåbpå{\ displaystyle ababa}

• En konjugasjonsklasse eller sirkulært ord eller krage er settet med konjugater av et ord.
  Noen ganger bemerkes et sirkulært ord av representant . For eksempel består konjugasjonsklassen av av de fem ordene .x{\ displaystyle x}(x){\ displaystyle (x)}påbpåpåb{\ displaystyle abaab}påbpåpåb,bpåpåbpå,påpåbpåb,påbpåbpå,bpåbpåpå{\ displaystyle abaab, baaba, aabab, ababa, babaa}

• En periode av et ord , hvor er symboler, er et heltall med slik at for . For eksempel har ordet punktene 5, 7 og 8.x=på1på2⋯påikke{\ displaystyle x = a_ {1} a_ {2} \ cdots a_ {n}}på1,på2,...,påikke{\ displaystyle a_ {1}, a_ {2}, \ ldots, a_ {n}}s{\ displaystyle p}1≤s≤ikke{\ displaystyle 1 \ leq p \ leq n}påJeg=påJeg+s{\ displaystyle a_ {i} = a_ {i + p}}Jeg=1,...,ikke-s{\ displaystyle i = 1, \ ldots, np}
  påbpåpåbpåbpå{\ displaystyle abaababa}

• Et periodisk ord er et ord hvis lengde er minst to ganger minimumsperioden. Et kvadrat , det vil si et ord av formen, er periodisk. Ordet er periodisk mens ordet ikke er det.uu{\ displaystyle uu}påpåbpåbpåpåbpåbpå=(påpåbpåbpå)2på{\ displaystyle aababaababa = (aababa) ^ {2} a}påbpåpåbpåbpå{\ displaystyle abaababa}

• En kant av et ord er et ord som både er et ordentlig prefiks og et ordentlig suffiks av . For eksempel er kantene på ordet det tomme ordet, og . Hvis er en kant av et ord , så er en periode på . Et ord uten kantlinje er et ord hvis eneste kantlinje er det tomme ordet. Det er et ord hvis eneste periode er lengden.x{\ displaystyle x}y{\ displaystyle y}x{\ displaystyle x}
  påbpåpåbpåbpå{\ displaystyle abaababa}på,påbpå{\ displaystyle a, aba}y{\ displaystyle y}x{\ displaystyle x}|x|-|y|{\ displaystyle | x | - | y |}x{\ displaystyle x}

• Den blanding produkt ш av to ord og er settet av ord , hvor den og les er ord, som for eksempel og . For eksempel ш .x{\ displaystyle x}y{\ displaystyle y}x{\ displaystyle x}y{\ displaystyle y}x1y1x2y2⋯xikkeyikke{\ displaystyle x_ {1} y_ {1} x_ {2} y_ {2} \ cdots x_ {n} y_ {n}}xJeg{\ displaystyle x_ {i}}yJeg{\ displaystyle y_ {i}}x=x1x2...xikke{\ displaystyle x = x_ {1} x_ {2} \ prikker x_ {n}}y=y1y2...yikke{\ displaystyle y = y_ {1} y_ {2} \ prikker y_ {n}}
  påb{\ displaystyle ab}påb={påpåbb,påbpåb}{\ displaystyle ab = \ {aabb, abab \}}

• Den leksikografiske rekkefølgen på ordene er definert med utgangspunkt i en total rekkefølge på alfabetet. Det er den alfabetiske rekkefølgen, formelt gitt av hvis og bare hvis er prefikset til eller hvis , og for ord og symboler og med . For eksempel, for alfabetet som er dannet av og med , har vi .x≤y{\ displaystyle x \ leq y}x{\ displaystyle x}y{\ displaystyle y}x=zpåx′{\ displaystyle x = zax '}y=zby′{\ displaystyle y = zby '}z,x′,y′{\ displaystyle z, x ', y'}på{\ displaystyle a}b{\ displaystyle b}på<b{\ displaystyle a <b}0{\ displaystyle 0}1{\ displaystyle 1}0<1{\ displaystyle 0 <1}ε<0<00<000<01<1<10⋯{\ displaystyle \ varepsilon <0 <00 <000 <01 <1 <10 \ cdots}

Lemma fra Levi

Lemma Levi  -  Let , , , ord. Hvis , så finnes det et ord som , eller , . x{\ displaystyle x}y{\ displaystyle y}x′{\ displaystyle x '}y′{\ displaystyle y '}xy=x′y′{\ displaystyle xy = x'y '}z{\ displaystyle z}x=x′z{\ displaystyle x = x'z}y′=zy{\ displaystyle y '= zy}x′=xz{\ displaystyle x '= xz}y=zy′{\ displaystyle y = zy '}

En annen måte å uttrykke dette resultatet på er å si at hvis og begge er prefikser av et ord, så er prefikset til eller er prefikset til . x{\ displaystyle x}x′{\ displaystyle x '}x{\ displaystyle x}x′{\ displaystyle x '}x′{\ displaystyle x '}x{\ displaystyle x}

Et grunnleggende resultat

Følgende resultat karakteriserer ordene som pendler.

Teorem  -  La være to ord som ikke er imøtekommende. Følgende forhold er ekvivalente: x{\ displaystyle x}y{\ displaystyle y}

• xy=yx{\ displaystyle xy = yx},
• det er to heltall slik at ,ikke,m≥1{\ displaystyle n, m \ geq 1}xikke=ym{\ displaystyle x ^ {n} = y ^ {m}}
• det er et ord og to heltall som og .z{\ displaystyle z}s,q≥1{\ displaystyle p, q \ geq 1}x=zs{\ displaystyle x = z ^ {p}}y=zq{\ displaystyle y = z ^ {q}}

Blant konsekvensene er:

• Hvert ord er kraften til et enkelt primitivt ord.
• Bøyningene til et primitivt ord er i seg selv primitive.
• Bøyningsklassen til et primitivt ord av lengde har elementer.ikke{\ displaystyle n}ikke{\ displaystyle n}

Teoremet innrømmer en sterkere versjon:

Hvis og er to ikke-ordløse ord, og hvis det er noen ikke-triviell sammenheng mellom og , det vil si hvis det er en sammenheng x{\ displaystyle x}y{\ displaystyle y}x{\ displaystyle x}y{\ displaystyle y}

z1z2⋯zikke=z1′z2′⋯zm′{\ displaystyle z_ {1} z_ {2} \ cdots z_ {n} = z '_ {1} z' _ {2} \ cdots z '_ {m}}

hvor er enten eller og z1,z2,...,zikke,z1′,z2′,...,zm′{\ displaystyle z_ {1}, z_ {2}, \ ldots, z_ {n}, z '_ {1}, z' _ {2}, \ ldots, z '_ {m}}x{\ displaystyle x}y{\ displaystyle y}

z1≠z1′{\ displaystyle z_ {1} \ neq z '_ {1}}, da .xy=yx{\ displaystyle xy = yx}

Vi kan uttrykke disse resultatene i form av en ligning mellom ord  : den første sier at ligningen

XY=YX{\ displaystyle XY = YX}

i de ukjente har bare sykliske løsninger , det vil si hvor alle ordene er krefter for det samme ordet; den andre sier at enhver ligning i to variabler uten konstant bare har sykliske løsninger. X,Y{\ displaystyle X, Y}

En annen eiendom gjelder konjugasjon.

Teorem  -  La være ord uten ord. Så x,y,z{\ displaystyle x, y, z}

xy=yz{\ displaystyle xy = yz}

hvis og bare hvis det er et ord uten ord, et ord og et heltall som u{\ displaystyle u}v{\ displaystyle v}e≥0{\ displaystyle e \ geq 0}

x=uv,z=vu{\ displaystyle x = uv, z = vu}, og .y=(uv)eu=u(vu)e{\ displaystyle y = (uv) ^ {e} u = u (sett) ^ {e}}

Dette resultatet tilskrives noen ganger Lyndon og Schützenberger . Vi kan se denne påstanden som en beskrivelse av løsningene i ligningen

XY=YZ{\ displaystyle XY = YZ}

i tre variabler . X,Y,Z{\ displaystyle X, Y, Z}

Morfisme

En søknad

h:PÅ∗→B∗{\ displaystyle h: A ^ {*} \ til B ^ {*}}

er en morfisme eller en homomorfisme hvis den tilfredsstiller

h(xy)=h(x)h(y){\ displaystyle h (xy) = h (x) h (y)}

for alle ord . Enhver morfisme bestemmes av dens data på bokstavene i alfabetet . Faktisk, for et ord , det har vi x,y∈PÅ∗{\ displaystyle x, y \ i A ^ {*}}PÅ{\ displaystyle A}w=på1på2⋯påikke{\ displaystyle w = a_ {1} a_ {2} \ cdots a_ {n}}

h(w)=h(på1)h(på2)⋯h(påikke){\ displaystyle h (w) = h (a_ {1}) h (a_ {2}) \ cdots h (a_ {n})}.

I tillegg er bildet av det tomme ordet det tomme ordet:

h(ε)=ε{\ displaystyle h (\ varepsilon) = \ varepsilon}

fordi er det eneste ordet som er lik kvadratet, og ε{\ displaystyle \ varepsilon}

h(ε)=h(εε)=h(ε)h(ε){\ displaystyle h (\ varepsilon) = h (\ varepsilon \ varepsilon) = h (\ varepsilon) h (\ varepsilon)}.

Eksempler

Den Thue-Morse morphism gjør det mulig å definere den Prouhet-Thue-Morse sekvens . Det er morphism løpet definert av μ:PÅ∗→PÅ∗{\ displaystyle \ mu: A ^ {*} \ til A ^ {*}}PÅ={0,1}{\ displaystyle A = \ {0,1 \}}

μ(0)=01{\ displaystyle \ mu (0) = 01} μ(1)=10{\ displaystyle \ mu (1) = 10}

Ved å itere, får vi

μ(01)=0110{\ displaystyle \ mu (01) = 0110} μ(0110)=01101001{\ displaystyle \ mu (0110) = 01101001} μ(01101001)=0110100110010110{\ displaystyle \ mu (01101001) = 0110100110010110}

Den Fibonacci morphism definerer Fibonacci ord . Det er morfismen , med , definert av ϕ:PÅ∗→PÅ∗{\ displaystyle \ phi: A ^ {*} \ til A ^ {*}}PÅ={på,b}{\ displaystyle A = \ {a, b \}}

ϕ(på)=påb{\ displaystyle \ phi (a) = ab} ϕ(b)=på{\ displaystyle \ phi (b) = a}

Ved å itere, får vi

ϕ(påb)=påbpå{\ displaystyle \ phi (ab) = aba} ϕ(påbpå)=påbpåpåb{\ displaystyle \ phi (aba) = abaab} ϕ(påbpåpåb)=påbpåpåbpåbpå{\ displaystyle \ phi (abaab) = abaababa}

Spesielle morfismer

• En automorfisme er en sammenheng hvis og bare bildet av et symbol er et symbol.h:PÅ∗→PÅ∗{\ displaystyle h: A ^ {*} \ til A ^ {*}}
• En morphism er ikke-slette hvis bildet av et symbol er aldri tomt ord. Det tilsvarer å si at bildet av et ord alltid er minst like langt som startordet . Vi sier også ikke-avtagende morfisme , eller øker i vid forstand . Vi sier også at det er en morfisme av halvgrupper siden begrensningen til halvgruppen er med verdier i .h{\ displaystyle h}|h(w)|≥|w|{\ displaystyle | h (w) | \ geq | w |}PÅ+=PÅ∗∖ε{\ displaystyle A ^ {+} = A ^ {*} \ setminus \ varepsilon}B+{\ displaystyle B ^ {+}}
• En morfisme er alfabetisk hvis bildet av et symbol er et symbol eller det tomme ordet. Det tilsvarer å si at bildet av et ord alltid er kortere enn startordet.
• En morfisme er bokstavelig eller bokstav til bokstav eller bevarer lengden hvis bildet av et symbol er et symbol. Det tilsvarer å si at bildet av et ord har samme lengde som startordet.
• En morfisme er ensartet hvis bildene av symbolene alle har samme lengde. Hvis den vanlige lengden er , sa også at morfismen er - uniform . Thue-Morse morfismen er 2-uniform; Fibonacci-morfismen slettes ikke, og er ikke ensartet. En bokstavelig morfisme er 1-uniform.h{\ displaystyle h}k{\ displaystyle k}k{\ displaystyle k}
• En morfisme er symmetrisk hvis det er en sirkulær permutasjon av alfabetet som pendler med , dvs. slik ath:PÅ∗→PÅ∗{\ displaystyle h: A ^ {*} \ til A ^ {*}} s:PÅ→PÅ{\ displaystyle s: A \ til A}h{\ displaystyle h}h(s(på))=s(h(på)){\ displaystyle h (s (a)) = s (h (a))}for ethvert symbol . Her utvides til en automorfisme av . Denne formelen antyder at det er ensartet. Thue-Morse morfismen er symmetrisk.på{\ displaystyle a}s{\ displaystyle s}PÅ∗{\ displaystyle A ^ {*}}h{\ displaystyle h}

Merknader og referanser

Referanser

1. I engelskspråklig litteratur sier vi underord for faktor og spredt underord for underord.
2. Symbolet "ш" er bokstaven sha i det kyrilliske alfabetet . Unicode- tegnet U + 29E2 (SHUFFLE PRODUCT)) brukes også. I en matematisk formel kan vi også bruke \ text {ш}.
3. For å forstå dette eksemplet, la oss skrive bokstavene i det andre ordet med store bokstaver. Med denne konvensjonen har vi gjort det påb{\ displaystyle ab} ш PÅB={påbPÅB,påPÅbB,PÅpåbB,påPÅBb,PÅpåBb,PÅBpåb}{\ displaystyle AB = \ {abAB, aAbB, AabB, aABb, AaBb, ABab \}} og når vi kommer tilbake til små bokstaver, er det bare de to angitte ordene som er igjen.
4. Denne uttalelsen er faktisk den enkle delen. Det er en omvendt: hvis en monoid tilfredsstiller konklusjonen av lemmaet, og hvis det dessuten eksisterer en morfisme av i additivet monoid av naturlige heltall slik at , er M gratis (se Lothaire (1983), Oppgave 1.1.1).M{\ displaystyle M}λ{\ displaystyle \ lambda}M{\ displaystyle M}λ-1(0)=1{\ displaystyle \ lambda ^ {- 1} (0) = 1}
5. For eksempel i 2009 Shallit lærebok , 2.3 teoremer av Lyndon - Schützenberger.
6. Denne terminologien brukes av (i) Anna E. Frid , "  Arithmetical complexity of the symmetric D0L words  " , Theoretical Computer Science , vol.  306,2003, s.  535-542.

Relaterte artikler

• Formel (matematikk)
• Kombinatorikk av ord
• Sammenkobling
• Språkteori

Bibliografi

• Jean-Michel Autebert, algebraiske språk , Masson,1987, 278  s. ( ISBN  978-2-225-81087-9 )
• Olivier Carton, Formelle språk, beregningsevne og kompleksitet: bachelor- og mastergrad i matematikk eller informatikk, informatikk alternativ for aggregering av matematikk , Paris, Vuibert ,2008, 237  s. ( ISBN  978-2-7117-2077-4 )
• Maxime Crochemore , Christophe Hancart og Thierry Lecroq, Algorithmique du texte , Paris, Vuibert ,2004, 347  s. ( ISBN  2-7117-8628-5 )
• (en) M. Lothaire, Combinatorics on Words , vol.  17, Addison-Wesley Publishing Co., Reading, Mass.,1983, 238  s. ( ISBN  978-0-201-13516-9 , online presentasjon )- En annen, revidert utgave dukket opp av Cambridge University Press , i Cambridge Mathematical Library-samlingen, i 1997, ( ISBN  978-0521599245 ) .
• (en) Jeffrey Shallit, et andre kurs i formelle språk og automatteori , Cambridge University Press ,2009, 240  s. ( ISBN  978-0-521-86572-2 )

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">