nonterminalsoccurs

In formal language theory, the phrase nonterminal occurs refers to the presence of a nonterminal symbol within strings produced by a grammar. Let G = (N, Σ, P, S) be a context-free grammar, where N is the set of nonterminal symbols, Σ is the set of terminals, P is the set of production rules, and S is the start symbol. A sentential form α is any string over N ∪ Σ. A nonterminal A ∈ N occurs in α if α contains A as a symbol; equivalently, α can be written as x A y for some x, y ∈ (N ∪ Σ)*. A single sentential form may contain multiple occurrences of A, possibly at different positions.

During derivations, occurrences of nonterminals are transformed as productions are applied. If α ⇒* β is a derivation, the occurrences of a nonterminal in α may be replaced by the right-hand sides of chosen productions, producing new occurrences in β. Occurrence analysis is central to several grammar properties: a nonterminal may occur in some derivation from the start symbol or may become unproductive (unable to derive a string of terminals) or unreachable (never appearing in any derivation from S).

Common related notions include reachability (whether a nonterminal can occur in any sentential form derived from S) and productivity (whether it can derive a terminal string). A nonterminal is useful if it is both reachable and productive; otherwise it is often eliminated in grammar simplification. The concept of occurrences also underpins parsing algorithms and grammar transformations, where tracking where nonterminals appear helps determine applicable productions and the structure of derivations.