Programming Languages: Concepts and Implementation

2.2 Introduction to Formal Languages

An alphabet is a finite set of symbols denoted by Σ. A string is a combination of symbols, also called characters, over an alphabet. For instance, strings over the alphabet include a, aa, aaa, bb, aba, and abc. The empty string (i.e., a string of zero characters) is represented as ∈. The Kleene closure operator of an alphabet (i.e., Σ^*) represents the set of all possible strings that can be constructed through zero or more concatenations of characters from the alphabet. Thus, the set of all possible strings from the alphabet is Σ^*. While Σ is always finite, Σ^* is always infinite and always contains ∈. The ...