Коначни трансдуктор

Коначни трансдуктор (или коначни претварач, коначни преобличавач, те још и коначни претварач) је коначна машина са две траке: улазном и излазном.

Разликује се од обичног коначног аутомата, који има само једну траку. За аутомат се каже да препознаје ниску уколико посматрамо садржај његове траке као улаз. Другим речима, аутомат рачуна функцију која пресликава ниске у скуп {0,1}. Такође, може се рећи да аутомат генерише ниске, што значи да посматрамо његову траку као излазну траку. На овај начин, аутомат генерише формални језик, који је скуп ниски. Ова два виђења су еквивалентна: функција коју аутомат рачуна је управо функција која представља индикатор скупа ниски које аутомат препознаје. Класа језика генерисаних коначним аутоматима се назива класом регуларних језика.

Две траке код трансдуктора се обично посматрају као улазна и излазна трака. На овај начин посматрано, каже се да он трансдукује (преводи) садржај своје улазне траке у своју излазну траку, прихватањем ниске на улазу и генерисањем нове ниске на излазу. Трансдуктор овај процес може да спроводи недетерминистички, и тада може да произведе више од једног излаза за сваку улазну ниску. Уопштено посматрано, трансдуктор рачуна релацију између два формална језика. Класа релација које израчунавају коначни трансдуктори се назива класом рационалних релација.

Коначни трансдуктори се обично користе за истраживање и примену обраде природних језика у морфолошкој анализи.

Формална конструкција

Формално, коначни трансдуктор T је представљен уређеном шесторком (Q, Σ, Γ, I, F, δ) где је:

• Q коначан скуп, скуп стања;
• Σ коначан скуп, који се назива улазном азбуком;
• Γ коначан скуп, који се назива излазном азбуком;
• I подскуп од Q, скуп почетних стања;
• F подскуп од Q, скуп завршних стања; и
• $\delta \subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q$ (где је ε празна ниска) је релација прелаза.

Можемо да посматрамо (Q, δ) као усмерени граф, који се назива граф прелаза за T: скуп чворова је Q, а $(q,a,b,r)\in \delta$ значи да постоји означена грана која води из чвора q у чвор r. Такође се каже да је a улазна етикета а b је излазна етикета.

Могуће су и алтернативне дефиниције коначног трансдуктора, али се све могу свести на ову. Дефинишемо проширену релацију прелаза $\delta ^{*}$ као најмањи скуп такав да:

• $\delta \subseteq \delta ^{*}$;
• $(q,\epsilon ,\epsilon ,q)\in \delta ^{*}$ за сваки $q\in Q$; и
• ако $(q,x,y,r)\in \delta ^{*}$ и $(r,a,b,s)\in \delta$ тада $(q,xa,yb,s)\in \delta ^{*}$.

Проширена релација прелаза је у суштини рефлексивно транзитивно затворење графа прелаза који је повећан на начин да узима у обзир и ознаке ивица. Елементи релације $\delta ^{*}$ су познати као путеви. Ивичне ознаке пута се добијају надовезивањем ивичних ознака својих саставних прелаза у редоследу.

Понашање трансдуктора T је рационална релација [T] дефинисана на следећи начин: $x[T]y$ ако и само ако постоји $i\in I$ и $f\in F$ тако да $(i,x,y,f)\in \delta ^{*}$. Овиме кажемо да T трансдукује стринг $x\in \Sigma ^{*}$ у ниску $y\in \Gamma ^{*}$ ако постоји пут од почетног до коначног стања чија је улазна ознака x и излазна ознака y.

Операције над коначним трансдукторима

Следеће операције дефинисане над коначним аутоматима се такође могу применити и за коначне трансдукторе:

• Унија : За дате трансдукторе T и S, постоји трансдуктор $T\cup S$ такав да $x[T\cup S]y$ ако и само ако $x[T]y$ или $x[S]y$.

• Конкатенација (надовезивање): За дате трансдукторе T и S, постоји трансдуктор $T\cdot S$ такав да $wx[T\cdot S]yz$ ако и само ако $w[T]y$ и $x[S]z$.

• Клинијево затворење: За дати трансдуктор T, постоји трансдуктор $T^{*}$ са следећим особинама:

(1) $\epsilon [T^{*}]\epsilon$; (2) ако $w[T^{*}]y$ и $x[T]z$ тада $wx[T^{*}]yz$ ; и $x[T^{*}]y$ не вреди осим ако то не налажу (1) или (2).

Уочите да не постоји нотација пресека трансдуктора. Уместо тога, постоји операција композиције која је карактеристична за трансдукторе и чија конструкција је слична оној при пресеку аутомата. Композиција је дефинисана на следећи начин:

• За дати трансдуктор T над азбукама Σ и Γ и за трансдуктор S над азбукама Γ и Δ, постоји трансдуктор $T\circ S$ над Σ и Δ такав да је $x[T\circ S]z$ ако и само ако постоји стринг $y\in \Gamma ^{*}$ такав да важи $x[T]y$ и $y[S]z$.

Такође, може се направити пројекција неке од трака трансдуктора како би се добио аутомат. Постоје две функције пројекције: $\pi _{1}$ чува улазну траку и $\pi _{2}$ чува излазну траку. Прва пројекција, $\pi _{1}$, је дефинисана на следећи начин:

• За дати трансдуктор T, постоји коначан аутомат $\pi _{1}T$ такав да $\pi _{1}T$ прихвата x ако и само ако постоји стринг y за који је $x[T]y$.

Друга пројекција, $\pi _{2}$, је дефинисана на сличан начин.

Додатна својства коначних трансдуктора

• Одлучиво је да ли је релација [T] трансдуктора T празна.

• Одлучиво је да ли постоји стринг y такав да је x[T]y за дати стринг x.

• Неодлучиво је да ли су два трансдуктора еквивалентна.