Article · Wikipedia archive · Last revised Jun 1, 2026

Recursive transition network

A recursive transition network ("RTN") is a graph theoretical schematic used to represent the rules of a context-free grammar. RTNs have application to programming languages, natural language and lexical analysis. Any sentence that is constructed according to the rules of an RTN is said to be "well-formed". The structural elements of a well-formed sentence may also be well-formed sentences by themselves, or they may be simpler structures. This is why RTNs are described as recursive.

Last revised
Jun 1, 2026
Read time
≈ 1 min
Length
167 w
Citations
2
Source
Wikipedia ↗
A recursive transition network for "fancy nouns". Note that recursion is created by the nodes labelled "Fancy noun". source ↗

A recursive transition network ("RTN") is a graph theoretical schematic used to represent the rules of a context-free grammar. RTNs have application to programming languages, natural language and lexical analysis. Any sentence that is constructed according to the rules of an RTN1 is said to be "well-formed". The structural elements of a well-formed sentence may also be well-formed sentences by themselves, or they may be simpler structures. This is why RTNs are described as recursive.2

Notes and references

  1. A sentence is generated by a RTN by applying the generative rules specified in the RTN itself. These represent any set of rules or a function consisting of a finite number of steps.
  2. Ela Kumar (20 September 2008). Artificial Intelligence. I. K. International Pvt Ltd. pp. 324–. ISBN 978-81-906566-6-5.
See also

See also