Chapter 1 · Watch, then practise
Introduction
Express computational questions precisely using symbols, strings and languages.
3 questions · 3 with related videos. Matches are based on playlist titles; broader background matches are labeled.
What to study
- Alphabets and strings
- Empty string and empty language
- Language operations
- Computability and complexity
Chapter playlists
Choose a playlist
Notes
Introduction to Languages, Strings, and Operations
lydia · 5:44
Introduces strings and languages, supporting the distinction between an empty string and empty sets.
1. Three different objects
For Σ = {a, b}, distinguish ε, {ε} and ∅.
ε is a string containing zero symbols, so its length is zero. {ε} is a language containing exactly one string. ∅ is a language containing no strings. Σ* includes every finite string over the alphabet, including ε. Confusing an empty string with an empty set changes the meaning of language operations.
Introduction to Languages, Strings, and Operations
lydia · 5:44
Related language-operations lesson; the particular products of A and B are worked below.
2. Language operations
Let A = {a, bb} and B = {b}. Find AB, BA and A⁰.
AB = {ab, bbb}; BA = {ba, bbb}. Concatenation preserves order, so these languages differ. A⁰ = {ε}, because concatenating zero words contributes the empty string. A* is the union of all Aⁿ for n ≥ 0 and therefore always contains ε.
Why study theory of computation?
lydia · 3:26 · Background lecture
Choose a video · 2 lectures
Pairs the motivation for computability with an overview of computational complexity; this is conceptual background.
3. Two questions about algorithms
How does asking whether a problem is computable differ from asking about its complexity?
Computability asks whether an algorithm can solve every instance with the required behavior. Complexity studies resources, such as time or space, as a function of input size. A problem can have an algorithm that always terminates yet needs impractical resources on large inputs.