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}![PÅ](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
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}![10011](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6fcdac1253246cda2940c3b8639710c2afd11f2)
- 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 \}}![A = \ {a, b, c \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/06b9d8908ec344da80af17b035774ba65e9cc818)
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}![uv = abracadabra](https://wikimedia.org/api/rest_v1/media/math/render/svg/f040e0a1e6cb869d4e9b21920e9a0f1c92d80752)
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}![PÅ](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
Ordsettet på et alfabet er tradisjonelt notert .
PÅ{\ displaystyle A}
PÅ∗{\ displaystyle A ^ {*}}![A ^ {*}](https://wikimedia.org/api/rest_v1/media/math/render/svg/44e23745a51c2c2d8d91fd98c1cf721573747ece)
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}![i = 1, \ ldots, n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5726d00b79af1b4666a6319c45381579dc85a9a)
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}![w = ps](https://wikimedia.org/api/rest_v1/media/math/render/svg/fae6e5d6bb684a2b0a31013062e6c3c1996f67bc)
- 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}![i = 1, \ ldots, n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5726d00b79af1b4666a6319c45381579dc85a9a)
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}![w = ps](https://wikimedia.org/api/rest_v1/media/math/render/svg/fae6e5d6bb684a2b0a31013062e6c3c1996f67bc)
- 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}![1 \ leq i \ leq j \ leq n](https://wikimedia.org/api/rest_v1/media/math/render/svg/95763b48b784f1cd453a4dc4a2c2f39e22997a43)
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}![w = pxs](https://wikimedia.org/api/rest_v1/media/math/render/svg/e34cecf6dbc46cb51af6d1ef74a168e5bf63a82a)
- 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 = x_ {1} x_ {2} \ cdots x_ {n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b9b2499de5cf69e5362f3ccea46f726fcf5f965)
x{\ displaystyle x}
y{\ displaystyle y}
y{\ displaystyle y}
påpå{\ displaystyle aa}
påbpåvs.{\ displaystyle abac}![abac](https://wikimedia.org/api/rest_v1/media/math/render/svg/86d522cb45528be06a3079bbf5d6b94f25a0d762)
- 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}}![{\ tilde w} = a_ {n} \ cdots a_ {1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dcc2ac17f5faa1b1bcb248017510f5361da81b20)
påbpåvs.{\ displaystyle abac}
vs.påbpå{\ displaystyle caba}![caba](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a9549f6138f3a8fba388e51c89cb10b087743de)
- En palindrom er et ord som er lik speilbildet.
For eksempel er ordet et palindrom.påbpåvs.påbpå{\ displaystyle abacaba}![abacaba](https://wikimedia.org/api/rest_v1/media/math/render/svg/575e7db3ef3dbc08c81e4f6dce7118f63ad165aa)
- 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}![ikke](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
- 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}![Vi vil](https://wikimedia.org/api/rest_v1/media/math/render/svg/7298c23d3d7dc2d348c618ea63da88fe3da6cf40)
- 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}![y = sp](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f0a3d9992962992c2f15ecb0dd2995b591b7140)
påbpåpåb{\ displaystyle abaab}
påbpåbpå{\ displaystyle ababa}![abeba](https://wikimedia.org/api/rest_v1/media/math/render/svg/dabb033cacfff5cef0347ba592b1054edce9a48f)
- 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}![abaab, baaba, aabab, ababa, babaa](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef91ba59808cae42fa5af8de5ee108596593b21f)
- 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}![i = 1, \ ldots, np](https://wikimedia.org/api/rest_v1/media/math/render/svg/4699c722c107bcd49928301aa5309378a1399acf)
påbpåpåbpåbpå{\ displaystyle abaababa}![abaababa](https://wikimedia.org/api/rest_v1/media/math/render/svg/e641602f7b337c402fdb31840ab09f484d60953b)
- 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}![abaababa](https://wikimedia.org/api/rest_v1/media/math/render/svg/e641602f7b337c402fdb31840ab09f484d60953b)
- 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}![x](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4)
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}![x](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4)
- 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}}![y = y_1y_2 \ prikker y_n](https://wikimedia.org/api/rest_v1/media/math/render/svg/c066b063c41a8e696e3e98da08d0f5476afd9e48)
påb{\ displaystyle ab}
påb={påpåbb,påbpåb}{\ displaystyle ab = \ {aabb, abab \}}![ab = \ {aabb, abab \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/485aed17da786e1f6519630c95f1c533fd43663b)
- 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}![\ varepsilon <0 <00 <000 <01 <1 <10 \ cdots](https://wikimedia.org/api/rest_v1/media/math/render/svg/86c81cdc6bdd1c803ecb77380b2cc482fa1edf71)
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 '}![y = zy '](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7384f3cafb48435d7de348af3cefc90814677e0)
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}![x](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4)
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}![y](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a6208ec717213d4317e666f1ae872e00620a0d)
-
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}}![x ^ n = y ^ m](https://wikimedia.org/api/rest_v1/media/math/render/svg/e20ba850a1b8306c2120e8500b8a0477c7c7bdbb)
- 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}}![y = z ^ {q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14acea0d5fad6c67b50db4686a4e86a7fb32bcba)
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}![ikke](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
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}![y](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a6208ec717213d4317e666f1ae872e00620a0d)
z1z2⋯zikke=z1′z2′⋯zm′{\ displaystyle z_ {1} z_ {2} \ cdots z_ {n} = z '_ {1} z' _ {2} \ cdots z '_ {m}}![z_ {1} z_ {2} \ cdots z_ {n} = z '_ {1} z' _ {2} \ cdots z '_ {m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/169f53cc7a9a23b9439d97aa2e297cc6d30d7ba3)
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}![y](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a6208ec717213d4317e666f1ae872e00620a0d)
z1≠z1′{\ displaystyle z_ {1} \ neq z '_ {1}}
, da .xy=yx{\ displaystyle xy = yx}![xy = yx](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2b203fa309e89fccdbba22909c8418f6b229779)
Vi kan uttrykke disse resultatene i form av en ligning mellom ord : den første sier at ligningen
XY=YX{\ displaystyle XY = YX}![XY = YX](https://wikimedia.org/api/rest_v1/media/math/render/svg/543dd8aea552a72267833b6c99ac36e21bb52b2c)
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}![X, Y](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8705438171d938b7f59cd1bfa5b7d99b6afa5cd)
En annen eiendom gjelder konjugasjon.
Teorem - La være ord uten ord. Så
x,y,z{\ displaystyle x, y, z}![X Y Z](https://wikimedia.org/api/rest_v1/media/math/render/svg/bbeca34b28f569a407ef74a955d041df9f360268)
xy=yz{\ displaystyle xy = yz}![{\ displaystyle xy = yz}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40c6623c80ab31fe4d2edd1d6a5742760af66b85)
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}![{\ displaystyle e \ geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e0c917975fc4bfb0bd800ff8b4b3f34cf97c94df)
x=uv,z=vu{\ displaystyle x = uv, z = vu}![{\ displaystyle x = uv, z = vu}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90bfa511971232f7a0467ac0e1c16fee4b207451)
, 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}![{\ displaystyle XY = YZ}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2caf2b554069de00b09b9e985550674b4c0c85f)
i tre variabler .
X,Y,Z{\ displaystyle X, Y, Z}![X Y Z](https://wikimedia.org/api/rest_v1/media/math/render/svg/bcf4a8b48db1a32d24aabe164b07744069093225)
Morfisme
En søknad
h:PÅ∗→B∗{\ displaystyle h: A ^ {*} \ til B ^ {*}}![h: A ^ {*} \ til B ^ {*}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ea44eca3c712f1488b2aaa06114fb8f78c907d2)
er en morfisme eller en homomorfisme hvis den tilfredsstiller
h(xy)=h(x)h(y){\ displaystyle h (xy) = h (x) h (y)}![h (xy) = h (x) h (y)](https://wikimedia.org/api/rest_v1/media/math/render/svg/0095a7bfeb86e1413135a8e8c802acb95d72a52a)
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}}![w = a_ {1} a_ {2} \ cdots a_ {n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b8cc244cff5cefbaedcf8d8e6c911f537639008)
h(w)=h(på1)h(på2)⋯h(påikke){\ displaystyle h (w) = h (a_ {1}) h (a_ {2}) \ cdots h (a_ {n})}![h (w) = h (a_ {1}) h (a_ {2}) \ cdots h (a_ {n})](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a7f80600df401d37b2b0b5a931c173c8924e01c)
.
I tillegg er bildet av det tomme ordet det tomme ordet:
h(ε)=ε{\ displaystyle h (\ varepsilon) = \ varepsilon}![h (\ varepsilon) = \ varepsilon](https://wikimedia.org/api/rest_v1/media/math/render/svg/495025062e99d0da584d57c2a8f645969a14433d)
fordi er det eneste ordet som er lik kvadratet, og
ε{\ displaystyle \ varepsilon}![\ varepsilon](https://wikimedia.org/api/rest_v1/media/math/render/svg/a30c89172e5b88edbd45d3e2772c7f5e562e5173)
h(ε)=h(εε)=h(ε)h(ε){\ displaystyle h (\ varepsilon) = h (\ varepsilon \ varepsilon) = h (\ varepsilon) h (\ varepsilon)}![h (\ varepsilon) = h (\ varepsilon \ varepsilon) = h (\ varepsilon) h (\ varepsilon)](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c418097e871546b02e1fadb9d946a8c9a16112b)
.
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 \}}![A = \ {0.1 \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7dc05978e4bcea653fe166bdb90353188dce75d1)
μ(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 \}}![A = \ {a, b \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/469abae5074de5867f770aec58e32e30cad048d5)
ϕ(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 ^ {*}}
![h: A ^ {*} \ til A ^ {*}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a38b633a4ff5cb3191d3f667708b3da199793b38)
- 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 ^ {+}}![{\ displaystyle B ^ {+}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/731dc88dd44f84be3617c27615bcc6840c2aeeb0)
- 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}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
- 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}![h](https://wikimedia.org/api/rest_v1/media/math/render/svg/b26be3e694314bc90c3215047e4a2010c6ee184a)
Merknader og referanser
Referanser
-
I engelskspråklig litteratur sier vi underord for faktor og spredt underord for underord.
-
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 {ш}.
-
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.
-
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}
-
For eksempel i 2009 Shallit lærebok , 2.3 teoremer av Lyndon - Schützenberger.
-
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
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;">