An introduction to formal language theory
Choice Reviews Online · 1989
Definition 1 An alphabet is a set containing finitely many symbols. Conventionally, we refer to this alphabet as Σ. Example 1 Here are some alphabets. • Σ = {a, b}. • Σ = {a, b, c, d}. • Σ = {john, laughed,and}. Definition 2 The set of all sequences of finite length that can be constructed from a set Σ is called Σ∗. This set has infinitely many elements in it. Elements of Σ∗ are also called strings. Σ∗ is defined recursively as follows. 1. The base case: The empty string λ is an element of Σ∗. 2. The recursive case: If w ∈ Σ∗ and σ ∈ Σ then wσ ∈ Σ∗.