xAyB

xAyB is a symbolic pattern used in formal language theory and string templating to describe strings built from fixed segments with interposed variable parts. In this usage, x and y are fixed words over an alphabet, while A and B denote languages (sets of strings) or sublanguages. The pattern represents the set of all strings of the form x u y v, where u ranges over A and v ranges over B. Thus, xAyB denotes the concatenation x · A · y · B, interpreted as the language { x u y v | u ∈ A, v ∈ B }.

As a construct, xAyB is convenient for describing how larger languages are assembled from smaller parts. If A and B are regular languages, then the language xAyB is also regular, since concatenation with fixed strings preserves regularity. If A and B are context-free, their concatenation is context-free, so xAyB is context-free as well. The notion is often used to illustrate how fixed prefixes and suffixes interact with variable interior portions in a language.

In grammar notation, xAyB can be represented by a production of the form S → x A y B, where A and B are nonterminals and x, y are terminals. This expresses that every string in the target language can be derived by introducing strings from A after the fixed prefix x and before the fixed suffix y followed by strings from B.

Examples help illustrate the idea. Let x = "pre" and y = "post"; let A = { "a" } and B = { "" , "b" }. Then xAyB yields strings like "preapost" and "preapostb".

See also: formal languages, pattern languages, concatenation, regular languages, context-free grammars.