Thread automaton: Difference between revisions

Revision as of 05:38, 7 May 2014

Revision as of 05:46, 7 May 2014

Line 4:

==Formal definition==

A '''thread automaton''' consists of

* a set ''N'' of states,<ref group=note>called ''non-terminal symbols'' by Villemonte (2002), p.1r</ref>

* a set Σ of terminal symbols,

Line 13:

* a finite set Θ of transitions.

A '''path''' ''u''₁...''u''_''n'' ∈ ''U''^{[[Kleene star|*]]} is a string of path components ''u''_''i'' ∈ ''U''; ''n'' may be 0, with the empty path denoted by ε.

A '''thread''' has the form ''u''₁...''u''_''n'':''A'', where ''u''₁...''u''_''n'' ∈ ''U''^* is a path, and ''A'' ∈ ''N'' is a state.

A '''thread store''' ''S'' is a finite set of threads, viewed as a partial function from ''U''^* to ''N'', such that ''dom''(''S'') is [[closure (mathematics)|closed]] by [[prefix (computer science)|prefix]].

A thread automaton '''configuration''' is a triple ‹''l'',''p'',''S''›, where ''l'' denotes the current position in the input string, ''p'' is the active thread, and ''S'' is a thread store containing ''p''.

The '''initial configuration''' is ‹0,ε,{ε:''A''_''S''}›.

The '''final configuration''' is ‹''n'',''u'',{ε:''A''_''S'',''u'':''A''_''F''}›, where ''n'' is the length of the input string and ''u'' abbreviates δ(''A''_''S'').

A '''transition''' in the set Θ may have one of the following forms, and changes the current automaton configuration in the following way:

* '''SWAP''' ''B'' →_''a'' ''C'': &nbsp; consumes the input symbol ''a'', and changes the state of the active thread:

: changes the configuration from &nbsp; ‹''l'',''p'',''S''∪{''p'':''B''}› &nbsp; to &nbsp; ‹''l''+1,''p'',''S''∪{''p'':''C''}›

Line 35:

One may prove that δ(''B'')=''u'' for '''POP''' and '''SPOP''' transitions, and δ(''C'')=⊥ for '''SPUSH''' transitions.<ref>Villemonte (2002), p.1r-2r</ref>

An input string is '''accepted''' by the automaton if there is a sequence of transitions changing the initial into the final configuration.

==Notes==