Course contentsShow
← Computer Science
Lesson 1757 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

The Empty String and String Length

Introduce the empty string (ε or λ), string length notation, and properties of the empty string.

The Empty String and String Length

What you'll learn: You'll understand what the empty string is, how to measure string length, and why the empty string matters in formal language theory.


The Empty String

In formal language theory, the empty string is a string containing zero characters. It's denoted by special symbols:

  • ε (epsilon) — most common in academic texts
  • λ (lambda) — alternate notation

Think of it like an empty container: it exists as a valid string, but holds nothing inside. Just as zero is a number (not "no number"), the empty string is still a legitimate string in any alphabet.

String Length Notation

The length of a string is the count of symbols it contains, written as:

  • |w| = length of string w
  • |s| = length of string s

For example, if your alphabet is {a, b}:

  • |"ab"| = 2
  • |"aaa"| = 3
  • |"b"| = 1

Properties of the Empty String

The empty string has special properties:

  1. Length zero: |ε| = 0 — it contains no symbols
  2. Identity for concatenation: For any string w, concatenating with ε doesn't change it:
    • w · ε = w
    • ε · w = w
  3. Exists in every alphabet: No matter which alphabet you define, ε is always a valid string over that alphabet

Think of ε like adding zero in arithmetic: 5 + 0 = 5. Similarly, concatenating "hello" with the empty string still gives you "hello".


Key Takeaway: The empty string (ε or λ) is a valid string with length zero that acts as the identity element for string concatenation, playing a fundamental role in formal language definitions.