Thread automaton: Difference between revisions

Revision as of 14:44, 6 April 2014

Revision as of 14:46, 6 April 2014

Line 5:

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,

* a start state ''A''_''S'' ∈ ''N'',

Line 33:

* '''SPOP''' [''B''] ''D'': &nbsp; resumes the parent of the active thread:

: changes &nbsp; ‹''l'',''pu'',''S''∪{''p'':''B'',''pu'':''C''}› &nbsp; to &nbsp; ‹''l'',''p'',''S''∪{''p'':''D'',''pu'':''C''}› &nbsp; where δ(''C'')=⊥

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.