Pattern language (formal languages)  In theoretical computer science, a pattern language is a formal language that can be defined as the set of all particular instances of a string of constants and variables. Pattern Languages were introduced by Dana Angluin in the context of machine learning. Given a finite set Σ of constant symbols and a countable set "X" of variable symbols disjoint from Σ, a pattern is a finite non-empty string of symbols from Σ∪"X". The length of a pattern "p", denoted by |"p"|, is just the number of its symbols. The set of all patterns containing exactly "n" distinct variables (each of which may occur several times) is denoted by "P""n", the set of all patterns at all by "P"*. A substitution is a mapping "f": "P"* → "P"* such that If "p" = "f"("q") for some patterns "p", "q" ∈ "P"* and some substitution "f", then "p" is said to be less general than "q", written "p"≤"q"; in that case, necessarily |"p"| ≥ |"q"| holds. For a pattern "p", its language is defined as the set of all less general patterns that are built from constants only, formally: "L"("p") = { "s" ∈ Σ+ : "s" ≤ "p" }, where Σ+ denotes the set of all finite non-empty strings of symbols from Σ. For example, using the constants Σ = { 0, 1 } and the variables "X" = { "x", "y", "z", ... }, the pattern 0"x"10"xx"1 ∈"P"1 and "xxy" ∈"P"2 has length 7 and 3, respectively. An instance of the former pattern is 00"z"100"z"0"z"1 and 01"z"101"z"1"z"1, it is obtained by the substitution that maps "x" to 0"z" and to 1"z", respectively, and each other symbol to itself. Both 00"z"100"z"0"z"1 and 01"z"101"z"1"z"1 are also instances of "xxy". In fact, "L"(0"x"10"xx"1) is a subset of "L"("xxy").