Slovo (matematika)

V matematice nebo teoretická , je slovo, je jen důsledkem konečných prvků pořízené v sadě . Celá se nazývá abeceda , její části se nazývají symboly nebo písmena . Říkají, že je to bezpečné slovo . w{\ displaystyle w}NA{\ displaystyle A}NA{\ displaystyle A}w{\ displaystyle w} NA{\ displaystyle A}

Příklady

• „Binární slovo“. Je to slovo v abecedě se dvěma symboly, obecně známými a . Například binární vývoj přirozeného čísla nebo jeho binární zápis je sekvence číslic jeho reprezentace v základně . Binární zápis „devatenáctky“ tedy je .0{\ displaystyle 0}1{\ displaystyle 1}2{\ displaystyle 2}10011{\ displaystyle 10011}
• „Sekvence deoxyribonukleové kyseliny  “ (DNA). Je to slovo obecně tvořené řadou čtyř písmen odpovídajících čtyřem nukleotidům tvořícím řetězec DNA: A pro „adenin“, G pro „guanin“, T pro „thymin“, C pro „cytosin“.
• „  Protein  “ je makromolekula složená z řetězce aminokyselin . Existuje 20 aminokyselin. Jedná se tedy o slovo v abecedě o 20 symbolech.

Vlastnosti

Jedno slovo se píše jednodušeji:w=(na1,na2,...,nane){\ displaystyle w = (a_ {1}, a_ {2}, \ ldots, a_ {n})}w=na1na2⋯nane{\ displaystyle w = a_ {1} a_ {2} \ cdots a_ {n}}

Délka slova je počet poloh symboly, které ji tvoří: nad slovo je délka . Například slovo v abecedě má délku 7. Slovo může být prázdné. Jedná se o slovo délky 0. Často se uvádí ε. w{\ displaystyle w}ne{\ displaystyle n}nabnavs.nabna{\ displaystyle abacaba}NA={na,b,vs.}{\ displaystyle A = \ {a, b, c \}}

Zřetězení dvou slov a je slovo získaný uvedením začátku až do konce a . Například zřetězení a dává . Zřetězení je asociativní operace, ale nikoli komutativní. Jeho neutrálním prvkem je slovo prázdné. u{\ displaystyle u}proti{\ displaystyle v}uproti{\ displaystyle uv}u{\ displaystyle u}proti{\ displaystyle v}u=nabrnavs.na{\ displaystyle u = abraca}proti=dnabrna{\ displaystyle v = dabra}uproti=nabrnavs.nadnabrna{\ displaystyle uv = abracadabra}

Sada slov v abecedě , opatřená zřetězením, proto tvoří monoid . Jako algebraická struktura je to volný monoid ve smyslu univerzální algebry . To znamená, že jakékoli slovo je výsledkem zřetězení symbolů, které jej tvoří. NA{\ displaystyle A}

Sada slov v abecedě je tradičně známá . NA{\ displaystyle A}NA∗{\ displaystyle A ^ {*}}

Další terminologie

• Tyto prefixy na slova jsou slova e a pro . Na 5 předpony slova jsou: ε, , , a sám. Pokud vyloučíme prázdné slovo, mluvíme o neprázdné předpony , pokud vyloučíme samotné slovo, mluvíme o správné předponě . Ekvivalentně je slovo předponou slova, pokud existuje slovo jako .w=na1⋯nane{\ displaystyle w = a_ {1} \ cdots a_ {n}}ne+1{\ displaystyle n + 1}na1⋯nai{\ displaystyle a_ {1} \ cdots a_ {i}}i=1,...,ne{\ displaystyle i = 1, \ ldots, n}
  nabnavs.{\ displaystyle abac}na{\ displaystyle a}nab{\ displaystyle ab}nabna{\ displaystyle aba}nabnavs.{\ displaystyle abac}p{\ displaystyle p}w{\ displaystyle w}s{\ displaystyle s}w=ps{\ displaystyle w = ps}

• Tyto přípony ze slova jsou slova e a pro . 5 přípona slova jsou: slova , , , a ε. Ekvivalentně je slovo příponou slova, pokud existuje slovo jako .w=na1⋯nane{\ displaystyle w = a_ {1} \ cdots a_ {n}}ne+1{\ displaystyle n + 1}nai⋯nane{\ displaystyle a_ {i} \ cdots a_ {n}}i=1,...,ne{\ displaystyle i = 1, \ ldots, n}
  nabnavs.{\ displaystyle abac}nabnavs.{\ displaystyle abac}bnavs.{\ displaystyle bac}navs.{\ displaystyle ac}vs.{\ displaystyle c}s{\ displaystyle s}w{\ displaystyle w}p{\ displaystyle p}w=ps{\ displaystyle w = ps}

• Tyto faktory na slova jsou slova , pro . Faktory slova jsou slova ε, , , , , , , , a . Ekvivalentně je slovo faktorem slova, pokud existují slova jako .w=na1⋯nane{\ displaystyle w = a_ {1} \ cdots a_ {n}}nai⋯naj{\ displaystyle a_ {i} \ cdots a_ {j}}1≤i≤j≤ne{\ Displaystyle 1 \ leq já \ leq j \ leq n}
  nabnavs.{\ displaystyle abac}na{\ displaystyle a}b{\ displaystyle b}vs.{\ displaystyle c}nab{\ displaystyle ab}bna{\ displaystyle ba}navs.{\ displaystyle ac}nabna{\ displaystyle aba}bnavs.{\ displaystyle bac}nabnavs.{\ displaystyle abac}X{\ displaystyle x}w{\ displaystyle w}p,s{\ displaystyle p, s}w=pXs{\ displaystyle w = pxs}

• Slovo je podslovem slova, pokud existuje faktorizace do slov jako . Takto se získá odstraněním symbolů v . Například je podslov z .X{\ displaystyle x}y{\ displaystyle}y=z0X1z1X2⋯Xnezne{\ displaystyle y = z_ {0} x_ {1} z_ {1} x_ {2} \ cdots x_ {n} z_ {n}}z0,X1,z1,X2,...,Xne,zne{\ displaystyle z_ {0}, x_ {1}, z_ {1}, x_ {2}, \ ldots, x_ {n}, z_ {n}}X=X1X2⋯Xne{\ displaystyle x = x_ {1} x_ {2} \ cdots x_ {n}}
  X{\ displaystyle x}y{\ displaystyle}y{\ displaystyle}nana{\ displaystyle aa}nabnavs.{\ displaystyle abac}

• Obraz zrcadlo nebo návrat slovem je slovo . Například zrcadlovým obrazem slova je slovo .w=na1⋯nane{\ displaystyle w = a_ {1} \ cdots a_ {n}}w~=nane⋯na1{\ displaystyle {\ tilde {w}} = a_ {n} \ cdots a_ {1}}
  nabnavs.{\ displaystyle abac}vs.nabna{\ displaystyle caba}

• Palindrom je slovo, které se rovná jeho zrcadlového obrazu.
  Například toto slovo je palindrom.nabnavs.nabna{\ displaystyle abacaba}

• Slovo je celočíselná síla slova, pokud existuje kladné celé číslo , například ( opakovaně ).X{\ displaystyle x}y{\ displaystyle}ne{\ displaystyle n}X=yne{\ displaystyle x = y ^ {n}}y{\ displaystyle}ne{\ displaystyle n}

• Slovo je primitivní, pokud to není celá síla jiného slova.
  Například slovo není primitivní, protože jde o druhou mocninu slova .bÓnebÓne{\ displaystyle bonbon}bÓne{\ displaystyle dobrý}

• Dvě slova a jsou konjugovaná, pokud existují slova a jako a . Například slova a jsou konjugovaná. Konjugace je vztah ekvivalence .X{\ displaystyle x}y{\ displaystyle}p{\ displaystyle p}s{\ displaystyle s}X=ps{\ displaystyle x = ps}y=sp{\ displaystyle y = sp}
  nabnanab{\ displaystyle abaab}nabnabna{\ displaystyle ababa}

• Třída konjugace nebo kruhový slovo nebo límec je množina konjugátů slova. Někdy je uvedeno
  kruhové slovo zástupce . Například třída konjugace je tvořena pěti slovy .X{\ displaystyle x}(X){\ displaystyle (x)}nabnanab{\ displaystyle abaab}nabnanab,bnanabna,nanabnab,nabnabna,bnabnana{\ displaystyle abaab, baaba, aabab, ababa, babaa}

• Období ze slova , kde jsou symboly, je celé číslo, se tak, že pro . Například slovo má tečky 5, 7 a 8.X=na1na2⋯nane{\ displaystyle x = a_ {1} a_ {2} \ cdots a_ {n}}na1,na2,...,nane{\ displaystyle a_ {1}, a_ {2}, \ ldots, a_ {n}}p{\ displaystyle p}1≤p≤ne{\ Displaystyle 1 \ leq p \ leq n}nai=nai+p{\ displaystyle a_ {i} = a_ {i + p}}i=1,...,ne-p{\ displaystyle i = 1, \ ldots, np}
  nabnanabnabna{\ displaystyle abaababa}

• Periodický slovo je slovo, která je alespoň dvakrát jeho minimální doba délka. Čtverec , to znamená, že slovo formuláře je periodický. Slovo je periodické, zatímco slovo není.uu{\ displaystyle uu}nanabnabnanabnabna=(nanabnabna)2na{\ displaystyle aababaababa = (aababa) ^ {2} a}nabnanabnabna{\ displaystyle abaababa}

• Hrana slovem je slovo , které je jak správný prefix a správné přípony . Například okraje slova jsou prázdné slovo a . Pokud je hrana slova , pak je to období . Slovo bez ohraničení je slovo, jehož jediným ohraničením je prázdné slovo. Je to slovo, jehož jedinou tečkou je jeho délka.X{\ displaystyle x}y{\ displaystyle}X{\ displaystyle x}
  nabnanabnabna{\ displaystyle abaababa}na,nabna{\ displaystyle a, aba}y{\ displaystyle}X{\ displaystyle x}|X|-|y|{\ displaystyle | x | - | y |}X{\ displaystyle x}

• Produkt směsi ш dvou slov a je množina slov , kde a les jsou slova, například a . Například ш .X{\ displaystyle x}y{\ displaystyle}X{\ displaystyle x}y{\ displaystyle}X1y1X2y2⋯Xneyne{\ displaystyle x_ {1} y_ {1} x_ {2} y_ {2} \ cdots x_ {n} y_ {n}}Xi{\ displaystyle x_ {i}}yi{\ displaystyle y_ {i}}X=X1X2...Xne{\ displaystyle x = x_ {1} x_ {2} \ tečky x_ {n}}y=y1y2...yne{\ displaystyle y = y_ {1} y_ {2} \ tečky y_ {n}}
  nab{\ displaystyle ab}nab={nanabb,nabnab}{\ displaystyle ab = \ {aabb, abab \}}

• Lexikografické uspořádání na slova je definován od celkového pořadí na abecedě. Je to abecední pořadí, formálně dané tím, zda a pouze pokud je předpona nebo if , a pro slova a symboly a s . Například pro abecedu tvořenou a s , máme .X≤y{\ displaystyle x \ leq y}X{\ displaystyle x}y{\ displaystyle}X=znaX′{\ displaystyle x = zax '}y=zby′{\ displaystyle y = zby '}z,X′,y′{\ displaystyle z, x ', y'}na{\ displaystyle a}b{\ displaystyle b}na<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 z Levi

Lemma Levi  -  Let , , , slova. -Li , pak existuje jediné slovo jako , nebo , . X{\ displaystyle x}y{\ displaystyle}X′{\ displaystyle x '}y′{\ displaystyle '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 '}

Dalším způsobem, jak vyjádřit tento výsledek, je říci, že pokud a jsou obě předpony slova, pak buď je předpona nebo je předpona . X{\ displaystyle x}X′{\ displaystyle x '}X{\ displaystyle x}X′{\ displaystyle x '}X′{\ displaystyle x '}X{\ displaystyle x}

Zásadní výsledek

Následující výsledek charakterizuje slova, která dojíždějí.

Věta  -  Dovolit a být dvě neprázdná slova. Následující podmínky jsou ekvivalentní: X{\ displaystyle x}y{\ displaystyle}

• Xy=yX{\ displaystyle xy = yx},
• existují dvě celá čísla taková, že ,ne,m≥1{\ displaystyle n, m \ geq 1}Xne=ym{\ displaystyle x ^ {n} = y ^ {m}}
• existuje slovo a dvě celá čísla jako a .z{\ displaystyle z}p,q≥1{\ displaystyle p, q \ geq 1}X=zp{\ displaystyle x = z ^ {p}}y=zq{\ displaystyle y = z ^ {q}}

Mezi důsledky patří:

• Každé slovo je silou jediného primitivního slova.
• Konjugáty primitivního slova jsou samy o sobě primitivní.
• Konjugační třída primitivního slova délky obsahuje prvky.ne{\ displaystyle n}ne{\ displaystyle n}

Věta připouští silnější verzi:

Jsou - li a jsou dvě neprázdná slova, a pokud existuje nějaký netriviální vztah mezi a , tj. Pokud existuje vztah X{\ displaystyle x}y{\ displaystyle}X{\ displaystyle x}y{\ displaystyle}

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

kde jsou buď nebo a z1,z2,...,zne,z1′,z2′,...,zm′{\ displaystyle z_ {1}, z_ {2}, \ ldots, z_ {n}, z '_ {1}, z' _ {2}, \ ldots, z '_ {m}}X{\ displaystyle x}y{\ displaystyle}

z1≠z1′{\ displaystyle z_ {1} \ neq z '_ {1}}tedy .Xy=yX{\ displaystyle xy = yx}

Tyto výsledky můžeme vyjádřit pomocí rovnice mezi slovy  : první říká, že rovnice

XY=YX{\ displaystyle XY = YX}

v neznámém má pouze cyklická řešení , to znamená, že všechna slova jsou mocninami stejného slova; druhý říká, že jakákoli rovnice ve dvou proměnných bez konstanty má pouze cyklická řešení. X,Y{\ displaystyle X, Y}

Další vlastnost se týká konjugace.

Věta  -  Nechť jsou neprázdná slova. Tak X,y,z{\ displaystyle x, y, z}

Xy=yz{\ displaystyle xy = yz}

právě když existuje neprázdné slovo, slovo a celé číslo jako např u{\ displaystyle u}proti{\ displaystyle v}E≥0{\ displaystyle e \ geq 0}

X=uproti,z=protiu{\ displaystyle x = uv, z = vu}A .y=(uproti)Eu=u(protiu)E{\ displaystyle y = (uv) ^ {e} u = u (vidět) ^ {e}}

Tento výsledek se někdy připisuje Lyndonovi a Schützenbergerovi . Toto tvrzení můžeme vidět jako popis řešení rovnice

XY=YZ{\ displaystyle XY = YZ}

ve třech proměnných . X,Y,Z{\ displaystyle X, Y, Z}

Morfismus

Aplikace

h:NA∗→B∗{\ displaystyle h: A ^ {*} \ do B ^ {*}}

je morfismus nebo homomorfismus, pokud to vyhovuje

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

pro všechna slova . Jakýkoli morfismus je určen jeho údaji o písmenech abecedy . Opravdu, na slovo , máme X,y∈NA∗{\ displaystyle x, y \ v A ^ {*}}NA{\ displaystyle A}w=na1na2⋯nane{\ displaystyle w = a_ {1} a_ {2} \ cdots a_ {n}}

h(w)=h(na1)h(na2)⋯h(nane){\ displaystyle h (w) = h (a_ {1}) h (a_ {2}) \ cdots h (a_ {n})}.

Obrázek prázdného slova je navíc prázdným slovem:

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

protože je jediné slovo rovnající se jeho čtverci a ε{\ displaystyle \ varepsilon}

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

Příklady

Thue-Morse morfismus umožňuje definovat sekvence Prouhet-Thue-Morse . Je to morfismus nad definovaný μ:NA∗→NA∗{\ displaystyle \ mu: A ^ {*} \ do A ^ {*}}NA={0,1}{\ displaystyle A = \ {0,1 \}}

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

Opakováním získáme

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

Fibonacci morphism definuje slovo Fibonacci . Je to morphism s , definovaný ϕ:NA∗→NA∗{\ displaystyle \ phi: A ^ {*} \ do A ^ {*}}NA={na,b}{\ displaystyle A = \ {a, b \}}

ϕ(na)=nab{\ displaystyle \ phi (a) = ab} ϕ(b)=na{\ displaystyle \ phi (b) = a}

Opakováním získáme

ϕ(nab)=nabna{\ displaystyle \ phi (ab) = aba} ϕ(nabna)=nabnanab{\ displaystyle \ phi (aba) = abaab} ϕ(nabnanab)=nabnanabnabna{\ displaystyle \ phi (abaab) = abaababa}

Zvláštní morfismy

• Automorphism je bijection jestliže a jediný obraz symbolu je symbol.h:NA∗→NA∗{\ displaystyle h: A ^ {*} \ do A ^ {*}}
• Morfismus se nevymaže, pokud obraz symbolu nikdy není prázdným slovem. Dá se říci, že obraz slova je vždy alespoň tak dlouhý jako počáteční slovo . Říkáme také neklesající morfismus nebo rostoucí v širším slova smyslu . Také říkáme, že se jedná o morfismus poloviční skupiny, protože její omezení na poloviční skupinu má hodnoty .h{\ displaystyle h}|h(w)|≥|w|{\ displaystyle | h (w) | \ geq | w |}NA+=NA∗∖ε{\ displaystyle A ^ {+} = A ^ {*} \ setminus \ varepsilon}B+{\ displaystyle B ^ {+}}
• Morfismus je abecední, pokud je obrazem symbolu symbol nebo prázdné slovo. Je to ekvivalentní tvrzení, že obraz slova je vždy kratší než počáteční slovo.
• Morfismus je doslovný nebo písmeno od písmene nebo zachovává délku, pokud je obraz symbolu symbolem. Rovnocenně se dá říci, že obraz slova má stejnou délku jako počáteční slovo.
• Morfismus je jednotný, pokud mají všechny symboly stejné délky. Pokud je společná délka , také se říká, že morfismus je - jednotný . Morfismus Thue-Morse je 2 uniformní; Fibonacciho morfismus se nevymaže a není jednotný. Doslovný morfismus je 1 uniforma.h{\ displaystyle h}k{\ displaystyle k}k{\ displaystyle k}
• Morfismus je symetrický, pokud existuje kruhová permutace abecedy, která dojíždí , tj. Takováh:NA∗→NA∗{\ displaystyle h: A ^ {*} \ do A ^ {*}} s:NA→NA{\ displaystyle s: A \ až A}h{\ displaystyle h}h(s(na))=s(h(na)){\ displaystyle h (s (a)) = s (h (a))}pro jakýkoli symbol . Zde je rozšířena na automorfismus . Tento vzorec znamená, že je jednotný. Thue-Morseův morfismus je symetrický.na{\ displaystyle a}s{\ displaystyle s}NA∗{\ displaystyle A ^ {*}}h{\ displaystyle h}

Poznámky a odkazy

Reference

1. V literatuře v anglickém jazyce se říká subword pro faktor a rozptýlené subword pro subword.
2. Symbol "ш" je písmeno sha v azbuce . Unicode znaku je také používán U + 29E2 (SHUFFLE PRODUCT)). V matematickém vzorci můžeme také použít \ text {ш}.
3. Abychom pochopili tento příklad, zapíšeme písmena druhého slova velkými písmeny. S touto konvencí máme nab{\ displaystyle ab} ш NAB={nabNAB,naNAbB,NAnabB,naNABb,NAnaBb,NABnab}{\ displaystyle AB = \ {abAB, aAbB, AabB, aABb, AaBb, ABab \}} a když se vrátíme na malá písmena, zůstanou pouze uvedená dvě slova.
4. Toto prohlášení je ve skutečnosti snadná část. K dispozici je opačný: pokud monoid splňuje závěr lemmatu, a je-li navíc existuje morphism o v aditivní monoidu přírodních celá čísla taková, že , pak M je volný (viz Lothaire (1983), problém 1.1.1).M{\ displaystyle M}λ{\ displaystyle \ lambda}M{\ displaystyle M}λ-1(0)=1{\ displaystyle \ lambda ^ {- 1} (0) = 1}
5. Například v učebnici Shallit 2009 , 2.3 Věty Lyndona - Schützenberger.
6. Tuto terminologii používá (ne) Anna E. Frid , „  Aritmetická složitost symetrických slov D0L  “ , Theoretical Computer Science , sv.  306,2003, str.  535-542.

Související články

• Vzorec (matematika)
• Kombinatorika slov
• Zřetězení
• Teorie jazyka

Bibliografie

• Jean-Michel Autebert, algebraické jazyky , Masson,1987, 278  s. ( ISBN  978-2-225-81087-9 )
• Olivier Carton, Formální jazyky, vyčíslitelnost a složitost: bakalářský a magisterský titul z matematiky nebo informatiky, výpočetní technika možnost agregace matematiky , Paříž, Vuibert ,2008, 237  s. ( ISBN  978-2-7117-2077-4 )
• Maxime Crochemore , Christophe Hancart a Thierry Lecroq, Algorithmique du texte , Paříž, Vuibert ,2004, 347  s. ( ISBN  2-7117-8628-5 )
• (en) M. Lothaire, Combinatorics on Words , sv.  17, Addison-Wesley Publishing Co., Reading, Massachusetts,1983, 238  s. ( ISBN  978-0-201-13516-9 , online prezentace )- Druhé přepracované vydání vyšlo v Cambridge University Press ve sbírce Cambridge Mathematical Library v roce 1997 ( ISBN  978-0521599245 ) .
• (en) Jeffrey Shallit, druhý kurz formálních jazyků a teorie automatů , 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;">