Introduction
Mathematical preliminaries form the foundation of the Theory of Computation. Understanding these basic concepts is essential for studying automata theory, formal languages, and computational complexity. These concepts help us describe and analyze computational problems in a precise mathematical way.
In this section, we will study three fundamental building blocks:
- Alphabets: The basic symbols we use
- Strings: Sequences formed from these symbols
- Languages: Collections of strings with specific properties
Why Study Mathematical Preliminaries?
Before we can understand complex computational models like Turing Machines or Finite Automata, we need a clear mathematical framework. Think of it like learning the alphabet before reading books - these preliminaries are our computational alphabet.
Real-World Applications
- Programming Languages: Compilers use these concepts to understand source code
- Text Processing: Search engines and text editors use pattern matching based on these ideas
- Network Protocols: Communication systems are defined using formal languages
- DNA Sequencing: Biological sequences are analyzed using string operations
Key Components
The mathematical preliminaries consist of three interconnected concepts that build upon each other:
1. Alphabets (Σ)
An alphabet is a finite, non-empty set of symbols. It serves as the basic building block.
Examples:
- Σ₁ = {0, 1} (binary alphabet)
- Σ₂ = {a, b, c, …, z} (lowercase English letters)
- Σ₃ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} (decimal digits)
2. Strings
A string is a finite sequence of symbols from an alphabet. Strings are the “words” we form using our alphabet.
Examples over Σ = {0, 1}:
- w₁ = “010”
- w₂ = “1111”
- w₃ = "" (empty string, denoted by ε or λ)
3. Languages
A language is a set of strings formed from an alphabet. It can be finite or infinite.
Examples:
- L₁ = {0, 01, 011} (finite language)
- L₂ = {0ⁿ1ⁿ | n ≥ 0} (infinite language of strings with equal 0s and 1s)
Relationship Between Concepts
Alphabet → Strings → Languages
Σ → w → L- From an alphabet, we form strings
- A collection of strings forms a language
- Everything is built systematically from simple to complex
Important Notations
| Symbol | Meaning | Example |
|---|---|---|
| Σ | Alphabet | Σ = {a, b} |
| w | String | w = “abba” |
| L | Language | L = {a, ab, abb} |
| ε or λ | Empty string | Length = 0 |
| Σ* | All possible strings | Includes ε |
| Σ⁺ | All non-empty strings | Excludes ε |
| |w| | Length of string w | |“abc”| = 3 |
Exam Tips
- Remember: Alphabet → Strings → Languages (hierarchical)
- Always specify the alphabet when defining strings or languages
- Don’t confuse Σ* (includes empty string) with Σ⁺ (excludes empty string)
- Practice writing strings and languages in set notation
- Understand that the empty string (ε) is different from an empty set (∅)
Practice Problems
Problem 1: Given Σ = {0, 1}, write 5 strings of length 3.
Solution: 000, 001, 010, 011, 100 (and three more: 101, 110, 111)
Problem 2: Define a language of all strings that start with ‘1’ over Σ = {0, 1}.
Solution: L = {w | w starts with 1} = {1, 10, 11, 100, 101, 110, 111, 1000, …}
Summary
Mathematical preliminaries provide us with:
- A formal way to represent data (strings)
- A method to define sets of valid inputs (languages)
- A foundation for building computational models
These concepts will be used throughout the course in defining automata, grammars, and computational complexity.