Færdig transducer

I teoretisk datalogi inden for lingvistik , især inden for automatteori , er en endelig transducer (også kaldet finite state transducer af en bogstavelig oversættelse fra engelsk finite state transducer ) en endelig automat med output. Det er en udvidelse af endelige automater . De arbejder med ordene på et inputalfabet, og i stedet for blot at acceptere eller afvise ordet omdanner de det på en undertiden ikke-deterministisk måde til et eller flere ord på et outputalfabet. Dette muliggør sprogtransformationer og også forskellige anvendelser, såsom især den syntaktiske analyse af programmeringssprog, og morfologisk analyse eller fonologisk analyse inden for lingvistik .

En af de bemærkelsesværdige egenskaber ved endelige transducere er, at de omdanner rationelle sprog til rationelle sprog og algebraiske sprog til algebraiske sprog.

Formelle definitioner

En endelig transducer er en matematisk maskine, der transformerer ord. En sådan maskine er designet efter modellen af ​​finite automata med for hver overgang en ekstra etiket i form af et ord. Hver overgang har derfor to mærker. Dette er ofte repræsenteret ved skrivningen

q→ på|b r{\ displaystyle q {\ xrightarrow {\ a | b \}} r}

Symbolet er inputetiketten , symbolet er outputetiketten for overgangen. På en billedlig måde siges det, at transduceren "læser" symbolet og "skriver" symbolet, mens det går fra stat til stat . Ved at gentage denne handling læser en transducer et ord fra venstre mod højre på inputbåndet og skriver et ord på outputbåndet. på{\ displaystyle a}b{\ displaystyle b}på{\ displaystyle a}b{\ displaystyle b}q{\ displaystyle q}r{\ displaystyle r}

Transducerens finitude betyder endeligheden af ​​antallet af stater. Men som ofte i teoretisk datalogi er maskinerne - i princippet - ikke-deterministiske, det vil sige, at der er flere henrettelser, hvor det samme ord læses, men maskinens tilstande og de skrevne ord kan variere. de forskellige henrettelser.

Endelige transducere har mange teoretiske egenskaber og mange praktiske anvendelser, for eksempel inden for kompilering , talegenkendelse og lingvistik .

Færdig transducer

En endelig transducer er defineret med en 6-uple

T=(Σ1,Σ2,Q,jeg,F,δ){\ displaystyle T = (\ Sigma _ {1}, \ Sigma _ {2}, Q, I, F, \ delta)}, eller:

• Σ1{\ displaystyle \ Sigma _ {1}}er det endelige input-alfabet  ;

• Σ2{\ displaystyle \ Sigma _ {2}}er det færdige output-alfabet  ;

• Q{\ displaystyle Q}er det endelige sæt stater  ;

• jeg⊆Q{\ displaystyle I \ subseteq Q}er sæt oprindelige tilstande  ;

• F⊆Q{\ displaystyle F \ subseteq Q}er sæt af endelige stater  ;

• δ{\ displaystyle \ delta} er overgangstabellen: det er en delmængde af Q×(Σ1∪{ε})×(Σ2∪{ε})×Q{\ displaystyle Q \ times (\ Sigma _ {1} \ cup \ {\ varepsilon \}) \ times (\ Sigma _ {2} \ cup \ {\ varepsilon \}) \ times Q}hvor er det tomme ord.ε{\ displaystyle \ varepsilon}

Egenskaben betyder, at der er en tilstand- til- tilstand-overgang, hvorved symbolet læses på inputbåndet, og symbolet skrives på outputbåndet. Dette er ofte repræsenteret af notationen (q,på,b,r)∈δ{\ displaystyle (q, a, b, r) \ in \ delta}q{\ displaystyle q}r{\ displaystyle r}på∈Σ1∪{ε}{\ displaystyle a \ in \ Sigma _ {1} \ cup \ {\ varepsilon \}}b∈Σ2∪{ε}{\ displaystyle b \ in \ Sigma _ {2} \ cup \ {\ varepsilon \}}

q→på|br{\ displaystyle q \, {\ xrightarrow {a | b}} \, r}

Symbolet er inputetiketten , symbolet er outputetiketten for overgangen. på{\ displaystyle a}b{\ displaystyle b}

Hvis for alt , siges transduceren T at være funktionel. |T(w)|≤1{\ displaystyle | T (w) | \ leq 1}w∈Σ1∗{\ displaystyle w \ in {\ Sigma _ {1}} ^ {*}}

Transitiv lukning

Den transitive lukning af er den mindste relation (for inkludering af relationer), der tilfredsstiller: δ∗{\ displaystyle \ delta ^ {*}}δ{\ displaystyle \ delta}

• δ∗⊆Q×Σ1∗×Σ2∗×Q{\ displaystyle \ delta ^ {*} \ subseteq Q \ times \ Sigma _ {1} ^ {*} \ times \ Sigma _ {2} ^ {*} \ times Q}

• δ⊆δ∗{\ displaystyle \ delta \ subseteq \ delta ^ {*}}

• ∀q∈Q,(q,ε,ε,q)∈δ∗{\ displaystyle \ forall q \ i Q, (q, \ varepsilon, \ varepsilon, q) \ i \ delta ^ {*}} (refleksivitet)

• Hvis og , så (transitivitet)(q,x,y,r)∈δ∗{\ displaystyle (q, x, y, r) \ in \ delta ^ {*}}(r,på,b,s)∈δ{\ displaystyle (r, a, b, s) \ in \ delta}(q,xpå,yb,s)∈δ∗{\ displaystyle (q, xa, yb, s) \ i \ delta ^ {*}}

Med andre ord betyder det, at der er en sti fra tilstand til tilstand, hvis inputetiket er ordet, og outputetiketten er ordet . En sti er vellykket, hvis og . (q,x,y,r)∈δ∗{\ displaystyle (q, x, y, r) \ in \ delta ^ {*}}q{\ displaystyle q}r{\ displaystyle r}x∈Σ1∗{\ displaystyle x \ in \ Sigma _ {1} ^ {*}}y∈Σ2∗{\ displaystyle y \ in \ Sigma _ {2} ^ {*}}q∈jeg{\ displaystyle q \ i I}r∈F{\ displaystyle r \ i F}

Rationelt forhold

Analogt med endelige automater , som genkender et sprog, et endeligt transducer genkender en relation, betegnet ved den kartesiske produkt af de to frie monoider. Vi har eller hvis og kun hvis det eksisterer og sådan sådan . Med andre ord vedrører hvis og kun hvis der er en vellykket sti, der læser og skriver . T{\ displaystyle T} [T]{\ displaystyle [T]}(x,y)∈[T]{\ displaystyle (x, y) \ i [T]}x[T]y{\ displaystyle x [T] y}s∈jeg{\ displaystyle p \ i I}r∈F{\ displaystyle r \ i F}(s,x,y,r)∈δ∗{\ displaystyle (p, x, y, r) \ in \ delta ^ {*}}x{\ displaystyle x}y{\ displaystyle y}x{\ displaystyle x}y{\ displaystyle y}

Variantdefinition

I en variant af definitionen, i stedet for at bede om, at etiketterne til overgangene er bogstaver eller det tomme ord, er ord autoriserede som etiketter på inputalfabetet resp. output-alfabetet.

De forskellige måder at se på en færdig transducer

En færdig transducer kan ses på flere måder, hvilket muliggør helt forskellige anvendelser.

Transducer ses som en automat

I det tilfælde hvor ingen af ​​transducerens etiketter er det tomme ord, kan vi se en transducer som et specielt tilfælde af endelige automater . Derefter kontrolleres automatiske klassiske egenskaber .

Det er tilstrækkeligt at overveje en automat, hvis alfabet er det kartesiske produkt af de to alfabeter . Σ=Σ1×Σ2{\ displaystyle \ Sigma = \ Sigma _ {1} \ times \ Sigma _ {2}}

Transducer ses som et rationelt forhold

At betragte en transducer som et rationelt forhold gør det muligt at etablere en primordial egenskab i undersøgelsen og brugen af ​​disse: lukning ved komposition .

Transducer operationer

Operationer arvet fra PLC'er

• Union: er og to endelige transducere. Vi definerer en endelig transducer, betegnet som .PÅ{\ displaystyle A}B{\ displaystyle B}PÅ∪B{\ displaystyle A \ cup B}[PÅ∪B]=[PÅ]∪[B]{\ displaystyle [A \ cup B] = [A] \ cup [B]}

• Sammenkædningsprodukt: lad og to transducere, så findes der en transducer bemærket som hvis og kun hvis og . Med andre ord .PÅ{\ displaystyle A}B{\ displaystyle B}PÅ⋅B{\ displaystyle A \ cdot B}xx′[PÅ⋅B]yy′{\ displaystyle xx '[A \ cdot B] åå'}x[PÅ]y{\ displaystyle x [A] y}x′[B]y′{\ displaystyle x '[B] y'}[PÅ⋅B]={(xx′,yy′)∣(x,y)∈[PÅ],(x′,y′)∈[B]}{\ displaystyle [A \ cdot B] = \ {(xx ', yy') \ mid (x, y) \ i [A], (x ', y') \ i [B] \}}

• Kleenes stjerne  : ja , så er der en bemærket transducer, der svarer til stjernen til sammenkædningsoperationen.T{\ displaystyle T}T∗{\ displaystyle T ^ {*}}

Opmærksomhed, skæringspunktet mellem rationelle relationer er ikke nødvendigvis rationelt (skæringspunktet mellem to relationer og er forholdet defineret af ) R{\ displaystyle R}R′{\ displaystyle R '}R″{\ displaystyle R ''}R″=R∩R′{\ displaystyle R '' = R \ cap R '}

Sammensætning

Overvej to transducere endelige og sådan, at outputalfabetet falder sammen med inputalfabetet . T1{\ displaystyle T_ {1}}T2{\ displaystyle T_ {2}}T1{\ displaystyle T_ {1}}T2{\ displaystyle T_ {2}}

Den forbindelse er defineret ved relationen  : T3=T2∘T1{\ displaystyle T_ {3} = T_ {2} \ circ T_ {1}}[T3]{\ displaystyle [T_ {3}]}

x[T3]y⇔∃z{\ displaystyle x [T_ {3}] y \ Leftrightarrow \ findes z}såsom og . x[T1]z{\ displaystyle x [T_ {1}] z}z[T2]y{\ displaystyle z [T_ {2}] y}

Det er vigtigt at bemærke, at sammensætningen af to færdige transducere stadig er en færdig transducer. Således gør sammensætningen det let at forberede transducere, der har en kompleks funktion fra simple transducere.

Fremskrivninger

• Venstre projektion: den venstre projektion af en relation er sættet . Lad være en endelig transducer. Den venstre projektion af forholdet er et rationelt sprog : der er en endelig automat, der genkender det; det er tilstrækkeligt at "glemme" outputetiketterne ved overgange af .R{\ displaystyle R}K={x∣∃y:(x,y)∈R}{\ displaystyle K = \ {x \ mid \ eksisterer y: (x, y) \ i R \}}T{\ displaystyle T}[T]{\ displaystyle [T]}T{\ displaystyle T}

• Højre projektion: Tilsvarende er den rigtige projektion af et rationelt forhold et rationelt sprog .

Andre egenskaber ved færdige transducere

• Problemet med at bestemme, om en færdig transducer er funktionel, kan afgøres.
• Problemet med at afgøre, om der findes et ord som for en given, kan afgøres.w{\ displaystyle w}T(x)=w{\ displaystyle T (x) = w}x{\ displaystyle x}
• Ækvivalensen mellem to endelige transducere kan generelt ikke afgøres. Det kan ikke desto mindre bestemmes i tilfælde af deterministiske endelige transducere og i det tilfælde, hvor transduceren udfører en delvis funktion.
• Hvis vi for en funktionel endelig transducer eller , kan vi konstruere en ækvivalent deterministisk funktionel finittransducer.T{\ displaystyle T}T(ϵ)=∅{\ displaystyle T (\ epsilon) = \ emptyset}T(ϵ)={ϵ}{\ displaystyle T (\ epsilon) = \ {\ epsilon \}}

Anvendelse til grammatisk analyse

I dette afsnit giver vi to eksempler på transducere. Givet en sætning er målet at generere en sekvens, der giver hvert ords grammatiske karakter i sætningen. For eksempel, hvis sætningen er "Alex kan lide fries", er målet at generere sekvensen NAVN VERB ARTIKELNAVN. Til dette er to transducere defineret.

Den første transducer, betegnet (for Lexicon), omdanner en række bogstaver efterfulgt af et mellemrum til et ord, hvis ordet er en del af leksikonet.L{\ displaystyle L}

En anden transducer, bemærket (for ordbog), omdanner et ord til dets grammatiske karakter (eller muligvis flere, hvis ordet har flere grammatiske karakterer).D{\ displaystyle D}

Så overvej bare sammensatte transducere . Da sammensætningen bevarer transducerernes funktion, tager denne nye transducer som input en sekvens af bogstaver og skriver som output en sekvens af grammatiske natur svarende til sætningens ord. T=D∗∘L∗{\ displaystyle T = D ^ {*} \ circ L ^ {*}}

Modeludvidelse: vægtet færdig transducer

Som med finite automata kan endelige transducere forbedres ved at veje dem. Metoden er også identisk med den, der anvendes til vægtet endelig automat.

En sådan optimering kan f.eks. Bruges i stavekontrol . Til det er det tilstrækkeligt at definere en afstand mellem ordene som d ( u , v ) = antal ændringer, der er nødvendige for at omdanne u til v . Det er derefter tilstrækkeligt at definere en transducer, der udfører elementære transformationer (bogstavændring, tilføjelse af et bogstav, sletning af et bogstav) ved korrekt vægtning af disse transformationer.

Så når et ord ikke findes i ordbogen, vil en sammenligning af dette ord med andre gennem den vægtede transducer afgøre, hvilket korrekt ord der er tættest.

Modelbegrænsninger

Afhængig af de betingelser, der pålægges transduceren, opnår den mere begrænsede forhold eller funktioner. Når transduceren er deterministisk ved indgangen, siges transduktionerne at være sekventielle; disse er funktioner, der kaldes sekventielle funktioner. Når input- og outputetiketterne for overgangene desuden er bogstaver, bevarer de udførte funktioner længderne; automatene er Mealys automater .

Relaterede artikler

• Mealys automat
• Moores automat
• Færdig automat
• Rationelt sprog
• Teori om automata
• Rationel transduktion

Referencer

1. Vi bemærker som sædvanlig de gratis monoide ord på alfabetet .Σ∗{\ displaystyle \ Sigma ^ {*}}Σ{\ displaystyle \ Sigma}
2. MP Schützenberger. Om rationelle relationer , Automata Theory and Formal Languages, 2nd GI Conference , Lecture Notes in Computer Science , bind 33, s. 209-213, 1975.
3. (i) Griffiths, T. Uopløseligheden af ​​ækvivalensproblemet for generaliseret Λ-fri ikke-deterministisk maskine , Journal of the Association for Computing Machinery 15, 1968 s. 409-413
4. (in) Eitan Mr. Gurari, Ækvivalensproblemet for deterministiske tovejs sekventielle transducere kan afgøres . SIAM J. Comput. , 11 (3): 448-452, 1982.
5. (in) Tero Harju Juhani Karhumäki, Ækvivalensproblemet med multitap finite automata , Theoretical Computer Science vol. 78, 1991, s. 347-355
6. Samuel Eilenberg. Automata, sprog og maskiner , bind A. Academic Press, 1974.
7. Jean-Eric Pin, kap.  I / 9 “Algoritmik og programmering. Finite automates ” , i Jacky Akoka og Isabelle Comyn-Wattiau (redaktører), Encyclopedia of computing and information systems , Paris, Vuibert, 2006( ISBN  978-2711748464 , HAL  hal-00143940 / dokument ) , s.  966-976
8. Jean-Éric Pin, "  Kort kursus om sekventielle funktioner  " , Sainte-Marie de Ré , LIAFA, CNRS og Université Denis Diderot,maj 2013(adgang til 3. august 2017 )

Yderligere bibliografi

• Stefan Gerdjikov , Stoyan Mihov og Klaus U. Schulz , ”  Rumeffektiv bimaskinkonstruktion baseret på equalizerakkumuleringsprincippet  ”, Theoretical Computer Science , vol.  790,2019, s.  80–95 ( ISSN  0304-3975 , DOI  10.1016 / j.tcs.2019.04.027 ).

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