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:
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.