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


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

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

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.