Transition relation

A transition relation (also transition relation ) is in computer science a relation that describes possible transitions. In transition systems and in automata , a transition relation indicates which state changes are possible. One then speaks of a state transition relation . A transition relation is not limited to a change of state. It can also describe transitions between configurations. Usually, relations are derived via configurations from state transition relations. However, it can also be used to define operational semantics .

If two states are in relation, a direct change from one state to the other is possible, otherwise not. It is also possible that the relation consists of further parameters, for example an input symbol, on which the change of state depends. The reflexive and transitive envelope of a transition relation is used for state transitions after entries of any length .

Transitions are also defined by functions . One then speaks of transition functions or transition functions.

definition

In the simplest case, a transition relation is a set of state pairs, the state set being referred to here as . ${\displaystyle \Delta }$ ${\displaystyle Z}$

${\displaystyle \Delta \subseteq Z\times Z}$

The pair then means that a transition from to is possible. Transitions between configurations are defined accordingly: ${\displaystyle (z,z')\in \Delta }$ ${\displaystyle z}$ ${\displaystyle z'}$ ${\displaystyle K}$

${\displaystyle \Delta _{K}\subseteq K\times K}$

If the state transition is dependent on an input symbol from the alphabet , the definition is as follows: ${\displaystyle \Sigma }$

${\displaystyle \Delta \subseteq Z\times \Sigma \times Z}$

The tuple means that a change from the state to the state is possible through the symbol . ${\displaystyle (z,a,z')\in \Delta }$ ${\displaystyle z}$ ${\displaystyle a}$ ${\displaystyle z'}$

The transition relation is often used in infix notation written as a derivative arrow: . ${\displaystyle z\rightarrow _{\Delta }z'}$

Transition function

A transition relation can also be represented as a transition function. Instead of relating a state to its possible successor states, the transition function maps a state to the set of possible successor states. These are multi-functions with image = original image (where ). ${\displaystyle \Delta }$ ${\displaystyle \delta }$ ${\displaystyle \delta ={\tilde {\Delta }}}$

In the simplest case, the definition is therefore a function that maps the state set into its power set .

${\displaystyle \delta \colon Z\to {\mathcal {P}}(Z)}$

The transition relation corresponds, for example, to the transition function ${\displaystyle \Delta _{1}=\{(z_{0},z_{1}),(z_{0},z_{2})\}}$

${\displaystyle \delta _{1}}$with . ${\displaystyle \delta _{1}(z_{0})=\{z_{1},z_{2}\}}$

If nondeterminism is excluded, i.e. there is an unambiguous successor state for every state, states can also be mapped to states:

${\displaystyle \delta \colon Z\to Z}$

If the transition depends on a symbol , the domain of the function is the set of pairs of state and input symbol. ${\displaystyle \Sigma }$

${\displaystyle \delta \colon Z\times \Sigma \to {\mathcal {P}}(Z)}$.

Formal languages

The transition relation of a formal grammar G (designated by the operator ) is a relation which states that the word right of the operator directly, ie by a single production , to the left of the operator from the word derived can be. ${\displaystyle \rightsquigarrow _{G}}$

For a formal grammar , the transition relation is then defined as follows: ${\displaystyle G=\left(V,\Sigma ,P,S\right)}$ ${\displaystyle \rightsquigarrow _{G}}$

${\displaystyle \rightsquigarrow _{G}\,\subseteq (V^{*}\setminus \Sigma ^{*})\times V^{*}}$Wherein , if , , with . ${\displaystyle u\rightsquigarrow _{G}v}$ ${\displaystyle u=xyz}$ ${\displaystyle v=xy'z}$ ${\displaystyle y\rightarrow y'\in P}$ ${\displaystyle x,z\in V^{*}}$

If it is clear what grammar it is, you often just write it . ${\displaystyle G}$ ${\displaystyle u\rightsquigarrow v}$

literature

• Katrin Erk, Lutz Priese: Theoretical Computer Science: A Comprehensive Introduction . 2., ext. Edition. Springer-Verlag, 2002, ISBN 3-540-42624-8 , pp. 64 ff .
• John C. Reynolds: Theories of Programming Languages . Cambridge University Press, 2009, ISBN 0-521-10697-4 , pp. 126 ( limited preview in Google Book search).