Automat závitů - Thread automaton

v teorie automatů, automat závitů (množné číslo: automaty) je rozšířený typ konečné automaty který rozpoznává a mírně kontextová jazyková třída nad sousední jazyky.^[1]

Formální definice

A automat závitů skládá se z

• sada N států,^{[poznámka 1]}
• sada Σ terminálních symbolů,
• počáteční stav A_S ∈ N,
• konečný stav A_F ∈ N,
• sada U komponent cesty,
• dílčí funkce δ: N → U^⊥, kde U^⊥ = U ∪ {⊥} pro ⊥ ∉ U,
• konečná množina přechodů.

A cesta u₁...u_n ∈ U^* je řetězec komponent cesty u_i ∈ U; n může být 0, s prázdnou cestou označenou ε.A vlákno má formu u₁...u_n:A, kde u₁...u_n ∈ U^* je cesta, a A ∈ N je stát úložiště vláken S je konečná sada vláken, která je považována za částečnou funkci z U^* na N, takový, že dom(S) je Zavřeno podle předpona.

Automat vláken konfigurace je trojitý ‹l,p,S›, Kde l označuje aktuální pozici ve vstupním řetězci, p je aktivní vlákno a S je úložiště vláken obsahující p.v počáteční konfigurace je ‹0, ε, {ε:A_S} › konečná konfigurace je <n,u, {ε:A_S,u:A_F} ›, Kde n je délka vstupního řetězce a u zkracuje δ (A_S).A přechod v sadě Θ může mít jednu z následujících forem a mění aktuální konfiguraci automatu následujícím způsobem:

• SWAP B →_A C: spotřebovává vstupní symbol A, a změní stav aktivního vlákna:

změní konfiguraci z ‹l,p,S∪{p:B} ›Do‹l+1,p,S∪{p:C}›

• SWAP B →_ε C: podobné, ale nespotřebovává žádný vstup:

Změny <l,p,S∪{p:B} ›Do‹l,p,S∪{p:C}›

• TLAČIT C: vytvoří nový podproces a pozastaví jeho nadřazené vlákno:

Změny <l,p,S∪{p:B} ›Do‹l,pu,S∪{p:B,pu:C} ›Kde u= δ (B) a puDoména (S)

• POP [B]C: ukončí aktivní vlákno a vrátí kontrolu nadřazenému:

Změny <l,pu,S∪{p:B,pu:C} ›Do‹l,p,S∪{p:C} ›Kde δ (C) = ⊥ a puDoména (S)

• SPUSH [C] D: obnoví pozastavený podproces aktivního vlákna:

Změny <l,p,S∪{p:B,pu:C} ›Do‹l,pu,S∪{p:B,pu:D} ›Kde u= δ (B)

• SPOP [B] D: obnoví rodiče aktivního vlákna:

Změny <l,pu,S∪{p:B,pu:C} ›Do‹l,p,S∪{p:D,pu:C} ›Kde δ (C)=⊥

Lze dokázat, že δ (B)=u pro POP a SPOP přechody a δ (C) = ⊥ pro SPUSH přechody.^[2]

Vstupní řetězec je přijato automatem, pokud existuje posloupnost přechodů měnících počáteční na konečnou konfiguraci.

Poznámky

Reference