Vinstgivande ord

Inom matematiken , närmare bestämt i formell språkteori , är de profinita orden en generalisering av begreppet finita ord till ett komplett topologiskt rum . Denna uppfattning tillåter användning av topologi för att studera språk och ändliga semigrupper . Till exempel används profinita ord för att ge en alternativ karaktärisering av den algebraiska föreställningen om en mängd finita semigrupper .

Definition

Låt A ett alfabet . Uppsättningen av profinita ord över A består av kompletteringen av ett metriskt utrymme vars domän är uppsättningen $A^{*}$ av ord över A . Avståndet som används för att definiera måtten ges med hjälp av begreppet separation av ord. Dessa begrepp är nu definierade.

Separation

Låt M och N vara monoider och låt p och q vara element i monoiden M . Låt φ vara en morfism av monoider från M till N . Det sägs att morfismen φ skiljer p och q om $\phi (p)\neq \phi (q)$ . Till exempel, morfismen ${\displaystyle \phi :A^{*}\to \mathbb {Z} /2\mathbb {Z} ,w\mapsto |w|(\operatörsnamn {mod} 2)} skickar ett ord$ till pariteten för dess längd skiljer orden ababa och abaa åt . Verkligen $\phi (ababa)=1\neq 0=\phi (abaa)$ .

Det sägs att N separerar p och q om det finns en morfism av monoider φ från M till N som separerar p och q . Med hjälp av föregående exempel $\mathbb {Z} /2\mathbb {Z}$ ababa och abaa åt . Mer allmänt $\mathbb {Z} /n\mathbb {Z}$ alla ord vars storlek inte är kongruenta modulo n . I allmänhet kan två distinkta ord separeras genom att använda monoid vars element är faktorerna p plus ett nytt element 0. Morfismen skickar prefix av p till sig själva och allt annat till 0.

Distans

Avståndet mellan två distinkta ord p och q definieras som inversen av storleken på den minsta monoid N som separerar p och q . Således är avståndet mellan ababa och abaa ${\frac {1}{2}}$ . Avståndet för p till sig självt definieras som 0.

Detta avstånd d är en ultrametrisk , det vill säga $d(x,z)\leq \max \left\{ d(x,y),d(y,z)\höger\}$ . Dessutom uppfyller den $d(uw,vw)\leq d(u,v)$ och $d(wu,wv)\leq d(u,v)$ . Eftersom vilket ord p som helst kan separeras från vilket annat ord som helst med en monoid med |p|+1 element, där |p| är längden av p , det följer att avståndet mellan p och vilket annat ord som helst är minst ${\frac {1}{|p|}}$ . Således är topologin som definieras av detta mått diskret .

Profinistisk topologi

Den profinita kompletteringen av $A^{*}$ , betecknad ${\widehat {A^{*}}}$ , är fullbordandet av uppsättningen ändliga ord under avståndet som definierats ovan . Kompletteringen bevarar den monoida strukturen.

Topologin på ${\widehat {A^{*}}}$ är kompakt .

Vilken monoid morfism som helst $\displaystyle \phi :A^{*}\to M}$${\widehat {\phi }}:{\widehat {A^{*}}}\to M$ , med M finit kan utökas unikt till en monoid morfism , och denna morfism är likformigt kontinuerlig (med vilken måttenhet som helst på $M$ som är kompatibel med den diskreta topologin). Dessutom ${\widehat {A^{*}}}$ det minst topologiska utrymmet med denna egenskap.

Vinstgivande ord

Ett profinitord är ett element av ${\widehat {A^{*}}}$ . Och ett profinat språk är en uppsättning profinita ord. Varje finita ord är ett profinita ord. Några exempel på profinita ord som inte är ändliga ges nu.

För m vilket ord som helst, låt $m^{\omega }$ beteckna ${\displaystyle \lim _{i\to \infty }m^{i!}} ,$ som finns för att $m^{i!}$ är en Cauchy-sekvens . Intuitivt, för att skilja $m^{i!}$ och $m^{i'!}$ , en monoid bör räknas minst upp till $\min(i,i')$ , och kräver därför minst $\min(i,i')$ element. Sedan $m^{i!}$ är en Cauchy-sekvens , $m^{\omega }$ är verkligen ett profinit ord.

är ordet $m^{\omega }$ idempotent . Detta beror på det faktum att för varje morfism $\phi :A^{*}\to N$ med N finita, $\phi (m^{i!})=\phi (m)^{i!}$ . Eftersom N är ändlig, för i stor nog, $\phi (m)^{i!}$ är idempotent och sekvensen är konstant.

På liknande sätt definieras $m^{\omega +1}$ och ${\displaystyle m^{\omega -1}} som$$\lim _{n\to \infty }m^{n!+1}$ och $\lim _{n\to \infty }m^{n!-1}$ respektive.

Profinata språk

Begreppet profinita språk tillåter en att relatera föreställningar om semigruppteori till föreställningar om topologi. Mer exakt, givet P ett profinistiskt språk, är följande påståenden likvärdiga:

• P är clopen .
• P känns igen ,
• Den syntaktiska kongruensen för P är clopen, som en delmängd av ${\widehat {A^{*}}}\times {\widehat {A^{*}}}$ .

Liknande påståenden gäller även för språk P av finita ord. Följande villkor är likvärdiga.

• $P$ känns igen (som en delmängd av $A^{*}$ ),
• stängningen av P , ${\overline {P}}$ , känns igen (som en delmängd av A $\displaystyle {\widehat {A^{*}}}}$ ), där
• $P=K\cap A^{*}$ , för vissa clopen K ,
• ${\overline {P}}$ är clopen.

Dessa karakteriseringar beror på det mer allmänna faktumet att om man tar stängningen av ett språk med ändliga ord och begränsar ett profinita språk till ändliga ord är omvända operationer när de tillämpas på igenkännbara språk.

Pin, Jean-Éric (2016-11-30). Matematiska grunder för automatteorin (PDF) . s. 130–139.

  Almeida, Jorge (1994). Finita semigrupper och universell algebra . River Edge, NJ: World Scientific Publishing Co. Inc. ISBN 981-02-1895-8 .