Introduction to Symbols and Strings

Symbols

• Symbols are the basic elements used to represent information.
• Examples include letters (a, b, c), numbers (0, 1, 2), and special characters.

Alphabets

• An alphabet is a collection of symbols denoted by the Greek letter Sigma (Σ).
• Examples:
  • Σ = {a, b, c}
  • Σ = {0, 1, 2, 3}
  • Σ = {d, e, f, g}

Strings

• A string is a sequence of symbols.
• Examples:
  • "a" is a string of length 1
  • "ab" is a string of length 2
  • "0101" is a string of length 4

Languages

• A language is a set of strings.
• Examples:
  • L1 = {00, 01, 10, 11} - the set of all strings of length 2 over the alphabet {0, 1}
  • L2 = {000, 001, 010, 011, 100, 101, 110, 111} - the set of all strings of length 3 over the alphabet {0, 1}
  • L3 = {000, 001, 010, 011,..., } - the set of all strings starting with "0" over the alphabet {0, 1}

Powers of Sigma

• Σ⁰ = {ε} - the set of all strings of length 0, represented by the empty string 'ε'
• Σ¹ = {0, 1} - the set of all strings of length 1
• Σ² = {00, 01, 10, 11} - the set of all strings of length 2
• Σ³ = {000, 001, 010, 011, 100, 101, 110, 111} - the set of all strings of length 3
• Σⁿ = {all strings of length n over alphabet Σ}

Cardinality

• Cardinality is the number of elements in a set.
• Cardinality of Σ⁰ = 1 (since there's only one string of length 0: ε)
• Cardinality of Σ¹ = 2 (since there are two strings of length 1: 0 and 1)
• Cardinality of Σ² = 4
• Cardinality of Σ³ = 8
• Cardinality of Σⁿ = 2ⁿ (when the alphabet has 2 symbols)

Sigma Star (Σ*)

• Σ* is the set of all possible strings of all lengths over the alphabet Σ.
• Σ* = Σ⁰ ∪ Σ¹ ∪ Σ² ∪ ... = {ε, 0, 1, 00, 01, 10, 11,...}
• Σ* is an infinite set.