Terminal Transition System

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 γ).

Example

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 σ⇒σ'.

References

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