Token - one letter or a sequence of letters which is treated as one item (if there is tokenization step).
Alphabet ( - sigma) is a finite, non-empty set of tokens. Example: .
String () is a finite sequence of tokens chosen from . Example: .
Language () a (possibly infinite) set of strings. Example: .
String length is a number of tokens in it: .
String concatenation: . Example: . Alternative notations: . In plain text space can be used:
Empty string: (epsilon). , .
Language concatenation: - Cartesian product of two sets. Example: .
String exponentiation: (k times). Example: .
Language exponentiation: (k times). , , . Example: - all binary words of length of 32.
String reversal: . Example: .
Language reversal: . Example: .
Language union: - set union. Other name: disjunction. Example: .
Language intersection: - set intersection. Other name: conjunction. Example: .
Language difference: - set difference. Example: .
Kleene closure: , . Example: ,
All finite strings (over alphabet ): , . Note: strictly speking I didn’t provide definition how to exponentiate alphabet - just treat it as language with strings of length 1.
“Trivial” language: . .
Empty language: . , .
- - for all
- - in a set
- - not in a set