A terminal transition system is a triple (Γ, ⇒, T) where (Γ, ⇒) is a transition system and T ⊆ Γ is a set called the terminal states or terminal configurations.

We say that γ' is a successor of γ if γ⇒γ'. If γ∈T then ¬∃γ':γ⇒γ' (there is no γ' such that γ' is a successor of γ).

Consider the context free grammar (N, Σ, P, S) where

- N is the finite set of non-terminal symbols;
- S ∈ N is the start symbol;
- Σ is the finite set of terminal symbols;
- P ⊆ N × (N ∪ Σ)
^{*}is the set of productions. A production (A, ab) is written A → aB.

And take N={E,V}, and Σ={λ, x, y, z}. and P to be the following set of productions:

- E → V
- E → E E
- E → λ V E
- V → x
- V → y
- V → z

The non-terminal E generates all members of Σ^{*} which happen to be
syntactically correct lambda calculus expressions which only use the variables x, y, and z.
The triple ((N ∪ Σ), ⇒, Σ^{*}) is a terminal transition system.
For any σ∈Σ there is no σ' such that σ⇒σ'.

R. Burstall. *Language Semantics and Implementation. Course Notes.* 1994.

Copyright © 2014 Barry Watson. All rights reserved.