Poloautomat - Semiautomaton

v matematika a teoretická informatika, a poloautomat je deterministický konečný automat se vstupy, ale bez výstupu. Skládá se z a soubor Q z státy, množina Σ nazývaná vstupní abeceda a funkce T: Q × Σ → Q nazývá se přechodová funkce.

S jakýmkoli poloautomatem je spojen monoidní volal charakteristický monoid, vstupní monoid, přechodový monoid nebo přechodový systém poloautomatu, který činy na množině států Q. Na to lze pohlížet buď jako na akci volný monoid z struny ve vstupní abecedě Σ nebo jako indukovaná transformační poloskupina z Q.

Ve starších knihách jako Clifford a Preston (1967) S-aktivity se nazývají „operandy“.

Transformační poloskupiny a monoidní akty

Hlavní článek: akce poloskupiny

A transformační poloskupina nebo transformační monoid je pár ${displaystyle (M, Q)}$ skládající se z a soubor Q (často nazývaný "soubor státy ") a a poloskupina nebo monoidní M z funkce nebo „transformace“, mapování Q pro sebe. Jsou to funkce v tom smyslu, že každý prvek m z M je mapa ${displaystyle mcolon Q o Q}$. Li s a t jsou dvě funkce transformační poloskupiny, jejich produkt poloskupiny je definován jako jejich složení funkce ${displaystyle (st) (q) = (scirc t) (q) = s (t (q))}$.

Někteří autoři považují „poloskupinu“ a „monoid“ za synonyma. Tady poloskupina nemusí mít prvek identity; monoid je poloskupina s prvkem identity (nazývaným také „jednotka“). Vzhledem k tomu, že pojem funkcí působících na množinu vždy zahrnuje pojem funkce identity, která při aplikaci na množinu nic nedělá, lze transformační semigroup vytvořit monoid přidáním funkce identity.

M-aktivity

Nechat M být monoidní a Q být neprázdnou sadou. Pokud existuje multiplikativní operace

${displaystyle mu colon Q imes M o Q}$

${displaystyle (q, m) mapsto qm = mu (q, m)}$

který splňuje vlastnosti

${displaystyle q1 = q}$

pro 1 jednotku monoidu a

${displaystyle q (st) = (qs) t}$

pro všechny ${displaystyle qin Q}$ a ${displaystyle s, tin M}$, pak trojnásobný ${displaystyle (Q, M, mu)}$ se nazývá a že jo M-akt nebo jednoduše a správné jednání. V dlouhé ruce ${displaystyle mu}$ je správné násobení prvků Q prvky M. Správný akt je často psán jako ${displaystyle Q_ {M}}$.

A levá věc je definován podobně, s

${displaystyle mu colon M imes Q o Q}$

${displaystyle (m, q) mapsto mq = mu (m, q)}$

a je často označován jako ${displaystyle, _ {M} Q}$.

An M-act úzce souvisí s transformačním monoidem. Nicméně prvky M nemusí to být funkce per se, jsou to jen prvky nějakého monoidu. Proto je třeba požadovat, aby akce ${displaystyle mu}$ být v souladu s množením v monoidu (tj. ${displaystyle mu (q, st) = mu (mu (q, s), t)}$), protože to obecně nemusí platit pro svévolné ${displaystyle mu}$, tak, jak to dělá pro funkční složení.

Jakmile člověk tento požadavek učiní, je zcela bezpečné upustit všechny závorky, protože monoidní produkt a působení monoidu na sadu jsou zcela asociativní. To zejména umožňuje reprezentovat prvky monoidu jako struny písmen ve smyslu informatiky pro slovo „řetězec“. Tato abstrakce pak umožňuje mluvit řetězcové operace obecně a nakonec vede ke konceptu formální jazyky jako složený z řetězců písmen.

Další rozdíl mezi M-act a transformační monoid je to pro M-akt Q, dva odlišné prvky monoidu mohou určovat stejnou transformaci Q. Pokud požadujeme, aby se tak nestalo, pak M-act je v podstatě stejný jako transformační monoid.

M-homomorfismus

Pro dva M-aktivity ${displaystyle Q_ {M}}$ a ${displaystyle B_ {M}}$ sdílení stejného monoidu ${displaystyle M}$, an M-homomorfismus ${displaystyle fcolon Q_ {M} o B_ {M}}$ je mapa ${displaystyle fcolon Q o B}$ takhle

${displaystyle f (qm) = f (q) m}$

pro všechny ${displaystyle qin Q}$ a ${displaystyle min M}$. Sada všech M-homomorfismus se běžně píše jako ${displaystyle mathrm {Hom} (Q_ {M}, B_ {M})}$ nebo ${displaystyle mathrm {Hom} _ {M} (Q, B)}$.

The M-akty a M-homomorfismy společně tvoří a kategorie volala M-Akt.

Poloautomata

A poloautomat je trojnásobek ${displaystyle (Q, Sigma, T)}$ kde ${displaystyle Sigma}$ je neprázdná množina, která se nazývá vstupní abeceda, Q je neprázdná množina, která se nazývá množina států, a T je přechodová funkce

${displaystyle Tcolon Q imes Sigma o Q.}$

Když množina států Q je konečná množina - nemusí být -, poloautomat může být považován za deterministický konečný automat ${displaystyle (Q, Sigma, T, q_ {0}, A)}$, ale bez počátečního stavu ${displaystyle q_ {0}}$ nebo sada přijímat státy A. Alternativně je to konečný stavový stroj který nemá žádný výstup a pouze vstup.

Jakýkoli poloautomat vyvolává čin monoida následujícím způsobem.

Nechat ${displaystyle Sigma ^ {*}}$ být volný monoid generované abeceda ${displaystyle Sigma}$ (aby byl horní index * chápán jako Kleene hvězda ); je to množina všech konečných délek struny složený z písmen v ${displaystyle Sigma}$.

Za každé slovo w v ${displaystyle Sigma ^ {*}}$, nechť ${displaystyle T_ {w} dvojtečka Q o Q}$ být funkcí definovanou rekurzivně následujícím způsobem pro všechny q v Q:

• Li ${displaystyle w = varepsilon}$, pak ${displaystyle T_ {varepsilon} (q) = q}$, takže prázdné slovo ${displaystyle varepsilon}$ nezmění stav.
• Li ${displaystyle w = sigma}$ je dopis dovnitř ${displaystyle Sigma}$, pak ${displaystyle T_ {sigma} (q) = T (q, sigma)}$.
• Li ${displaystyle w = sigma v}$ pro ${displaystyle sigma in Sigma}$ a ${displaystyle vin Sigma ^ {*}}$, pak ${displaystyle T_ {w} (q) = T_ {v} (T_ {sigma} (q))}$.

Nechat ${displaystyle M (Q, Sigma, T)}$ být set

${displaystyle M (Q, Sigma, T) = {T_ {w} vert win Sigma ^ {*}}.}$

Sada ${displaystyle M (Q, Sigma, T)}$ je uzavřen pod složení funkce; to znamená pro všechny ${displaystyle v, vyhrajte Sigma ^ {*}}$, jeden má ${displaystyle T_ {w} kruh T_ {v} = T_ {vw}}$. Také obsahuje ${displaystyle T_ {varepsilon}}$, který je funkce identity na Q. Protože složení funkce je asociativní, sada ${displaystyle M (Q, Sigma, T)}$ je monoid: nazývá se to vstupní monoid, charakteristický monoid, charakteristická poloskupina nebo přechodový monoid poloautomatu ${displaystyle (Q, Sigma, T)}$.

Vlastnosti

Pokud je soubor stavů Q je konečný, pak jsou přechodové funkce běžně reprezentovány jako tabulky přechodu stavu. Struktura všech možných přechodů řízených řetězci ve volném monoidu má grafické znázornění jako a de Bruijnův graf.

Sada států Q nemusí být konečné nebo dokonce spočetné. Jako příklad podtrhuje koncept poloautomata kvantové konečné automaty. Tady množina států Q jsou dány složitý projektivní prostor ${displaystyle mathbb {C} P ^ {n}}$a jednotlivé státy jsou označovány jako n-Stát qubits. Přechody stavu jsou dány unitární n×n matice. Vstupní abeceda ${displaystyle Sigma}$ zůstává konečný a ve hře zůstávají další typické obavy z teorie automatů. To znamená, že kvantová poloautomatizace lze jednoduše definovat jako trojitý ${displaystyle (mathbb {C} P ^ {n}, Sigma, {U_ {sigma _ {1}}, U_ {sigma _ {2}}, dotsc, U_ {sigma _ {p}},})}$ když abeceda ${displaystyle Sigma}$ má p písmena, takže existuje jedna unitární matice ${displaystyle U_ {sigma}}$ pro každé písmeno ${displaystyle sigma in Sigma}$. Takto vyjádřeno má kvantová poloautomatika mnoho geometrických zobecnění. Například si člověk může vzít a Riemannovský symetrický prostor namísto ${displaystyle mathbb {C} P ^ {n}}$a výběry ze skupiny izometrie jako přechodové funkce.

The syntaktický monoid a formální jazyk je izomorfní na přechodový monoid z minimální automat přijetí jazyka.

Reference

• A. H. Clifford a G. B. Preston, Algebraická teorie poloskupin. Americká matematická společnost, svazek 2 (1967), ISBN  978-0-8218-0272-4.
• F. Gecseg a I. Peak, Algebraická teorie automatů (1972), Akademiai Kiado, Budapešť.
• W. M. L. Holcombe, Teorie algebraických automatů (1982), Cambridge University Press
• J. M. Howie, Automaty a jazyky(1991), Clarendon Press, ISBN  0-19-853442-6.
• Mati Kilp, Ulrich Knauer, Alexander V. Mikhalov, Monoidy, činy a kategorie (2000), Walter de Gruyter, Berlín, ISBN  3-11-015248-7.
• Rudolf Lidl a Günter Pilz, Aplikovaná abstraktní algebra (1998), Springer, ISBN  978-0-387-98290-8