AG Algorithmisches Lernen
|
|
|
AG Algorithmisches Lernen
|
|
|
|
|
 Pattern LanguagesProject DescriptionA pattern -- a finite string that consists of variables and terminal symbols -- is a device for defining a formal language. It generates a word by a uniform substitution of all variables with arbitrary strings of terminal symbols, and, accordingly, its language is the set of all words that can be constructed by suchlike substitutions. For instance, the language generated by the pattern "x1 x1 a b x2" (with x1, x2 as variables and a, b as terminals) includes all words where the prefix can be split in two occurrences of the same string, followed by the string "a b" and concluded by an arbitrary suffix. Thus, the language of this pattern contains, among others, the words "a a a b a", "a b a b a b a b", "a b b b" (the latter example word is valid only if the substitution of variables with the empty word is allowed), whereas the following examples are not covered by it: "b a", "b b b b b", "b a a b a". Consequently, numerous regular and nonregular languages can be described by patterns in a compact and natural way. A survey article on pattern languages can be found in "G. Rozenberg and A. Salomaa (Eds.). Handbook of Formal Languages, volume 1. Springer-Verlag, 1997". | ||
| |||
