Chapter 8ARS & Confluenceslides.en.pdf:368-370

Transition Systems

States, actions, transitions

Def 3.1 — Transition systemDef 3.5 — Result relation

Concept

A transition system is one of the simplest models of "things that change". It
is a triple $\langle S, A, T \rangle$ where:

- $S$ is a set of states (the configurations a system can be in)
- $A$ is a set of actions (the things you can do)
- $T: S \times A \to \mathcal{P}(S)$ assigns to each state-action pair a set of
possible successor states

In words: from state $s$ , doing action $a$ lands you in some state in $T(s, a)$ .

If $|T(s,a)| \le 1$ for every $(s,a)$ the system is deterministic — every
action has at most one result. Otherwise it is non-deterministic.

From a transition system we can build the result relation $T_a$ which, given a
state, returns the set of states reachable by a single action (ignoring which
action):

T_a(s) := \{s' \mid \exists a \in A.\ s' \in T(s, a)\}

Why care? Transition systems model essentially everything that steps:
Turing machines, $\lambda$ -calculus, AI planning problems, network protocols,
game states, agents in an environment. Once you have states and transitions, you
can ask: "can I reach state $q$ from $s$ ?", "is every reachable state safe?",
"do two paths always converge?". Those questions become formal.

Example 1.3: C structs for grammars

Mathematical structures can be implemented in programming via record data structures (Def 1.2). In C:


struct grule {
    char *lhs;
    char **rhs;
    int   rhs_len;
};

struct grammar {
    char **nonterminals;
    int    n_n;
    char **terminals;
    int    n_t;
    struct grule *rules;
    int    n_p;
    char  *start;
};

The struct grule represents a single production rule: a left-hand side nonterminal lhs and a list rhs of right-hand side symbols. The struct grammar represents a full PSG (Def 1.1): nonterminals $N$ , terminals $\Sigma$ , productions $P$ , and start symbol $S$ .

Usage example:


struct grule r = { "S", (char*[]){"NP", "VP"}, 2 };
struct grammar G = {
    (char*[]){"S", "NP", "VP"}, 3,
    (char*[]){"john", "likes", "mary"}, 3,
    &r, 1,
    "S"
};

C structs give the data of a structure but not its axioms (e.g. 'every production has a nonterminal as its head') — those must be enforced by convention or runtime checks.

Example 1.4: OOP classes with inheritance

Object-oriented languages capture mathematical structures as classes, with inheritance modeling the is-a relationship between structures.


abstract class Magma {
    def op(a: Elem, b: Elem): Elem
}

class Semigroup extends Magma {
    // Adds associativity axiom:
    // forall a b c: op(op(a,b),c) == op(a,op(b,c))
}

class Monoid extends Semigroup {
    def identity: Elem
    // Adds identity axiom:
    // forall a: op(a, identity) == a
}

class Group extends Monoid {
    def inverse(a: Elem): Elem
    // Adds inverse axiom:
    // forall a: op(a, inverse(a)) == identity
}

Inheritance models the theory graph: Group is-a Monoid is-a Semigroup is-a Magma. Each subclass adds one axiom. Methods like op, identity, inverse implement the structure's operations.

However, OOP cannot enforce axioms at compile time (unlike dependent types or proof assistants). So OOP captures the shape of mathematical structures, but the axioms remain a programmer's responsibility.

Grammars as transition systems (Def 3.1 mapping)

A phrase-structure grammar $G = \langle N, \Sigma, P, S \rangle$ can be modelled as a transition system (Def 3.1) $\langle S, A, T \rangle$ where:
- States $S := (\Sigma \cup N)^*$ — all sentential forms.
- Actions $A := P$ — the production rules are the actions.
- Transition model $T(a, s) := \{s' \mid s \Rightarrow_a s'\}$ — applying action $a$ (production rule) to state $s$ produces new state(s) $s'$ in one step.

For a deterministic sub-grammar, $|T(a, s)| \leq 1$ for all $(a, s)$ . A string $w \in \Sigma^*$ is in $L(G)$ iff $S \Rightarrow^* w$ (zero or more steps from the start state).

Why this matters. Once we see $L(G)$ defined as reachability in a transition system, all transition-system theory applies: termination, confluence, complexity. We get a unified vocabulary for grammars, automata, ARS, and program semantics.

Worked example

Step 0 of 2

Practice — score 100% to advance

Multiple choice

What are the three components of a transition system

\langle S, A, T \rangle

When is a transition system deterministic?

What is the type of the result relation

T_a

Which is NOT an example of a transition system?

Why are transition systems useful in AI?

In OOP, inheritance between classes models the:

Fill in the blank

In the transition-system view of a grammar, production rules are the ___.

Match definitions

Match each concept on the left to its definition on the right.

Loading…