Introduction to Symbols and Strings

Study Notes

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.

Description

Explore the basics of symbols, alphabets, strings, and languages in this quiz. Understand how these elements represent information and form sequences. Test your knowledge on the various types of strings and their characteristics.