User:CircuitCraft/Definition:Semi-Thue Machine

Definition

Let $\Sigma$ be a finite set.

Let $\Sigma^*$ be the set of finite strings over $\Sigma$.

Let $\vdash \subset \Sigma^* \times \Sigma^*$ be a relation.

Let $\vdash^* \subset \Sigma^* \times \Sigma^*$ be defined as:

$\Gamma \vdash^* \Gamma'$

if and only if there exist $\alpha, \beta, \gamma, \gamma' \in \Sigma^*$ such that:

$\Gamma = \alpha \gamma \beta$

$\Gamma' = \alpha \gamma' \beta$

$\gamma \vdash \gamma'$

Let $M = \struct {\Sigma^*, \vdash^*}$ be an abstract machine.

Then $M$ is the semi-Thue machine over $\Sigma$ generated by $\vdash$.