Patterns in BP grammars

A pattern is a string of terminals and variables derived in a particular way: the derivation is obtained by replacing every variable with another pattern. For instance, if {a,b,c,...z} is a terminal alphabet, pattern "XfYXXY" may be derived as "abfYababY", "XfaZccXXaZcc", "abfaZccababaZcc", "abfaedccababaedcc", etc. using the following derivations:

X => ab , Y => aZcc , Z => ed

The set of all possible terminal derivations (e.g. "abfaedccababaedcc") of a pattern is called the language generated by this pattern. A pattern language is infinite unless some rules are used to define a limited number of acceptable derivations.

A grammar containing patterns may be called a pattern grammar. See for instance §4.5.