Inductive Proofs of String Properties

Hello! Welcome to our second lesson.

In our first lesson, we established the fundamental building blocks of computation theory: alphabets, strings, and formal languages. We defined a string as a finite sequence of symbols and a language as a set of strings. This provides the "what" of our study.

Today, we transition to the "how" by focusing on the operations we can perform on strings and, critically, how we can reason about them with mathematical certainty. The learning outcome for this lesson is to prove basic properties of string operations (concatenation, reversal, length) using mathematical induction.

Your experience with recursion in programming will be a great asset here. We will see that proofs by induction on recursively-defined structures (like strings) follow a pattern that is remarkably similar to writing a recursive function. Mastering this proof technique is essential, as it forms the bedrock for proving the correctness of the algorithms and machine constructions we will encounter throughout this course.

1. The Principle of Mathematical Induction

Before diving into strings, let's quickly refresh the core idea of mathematical induction. It's a powerful proof technique used to show that a property holds for an infinite set of cases (like all natural numbers, or all possible strings).

It works like a chain of dominoes:

Mathematical Induction: The Domino Effect — This image illustrates mathematical induction. To prove a statement P(n) for all n, you must: 1. **Base Case:** Prove P(0) is true (the first domino falls). 2. **Inductive Step:** Prove that if P(n) is true for an arbitrary n (one domino falls), then P(n+1) must also be true (it knocks over the next one). This guarantees the entire chain will fall.

When we apply this to strings, we don't induct on numbers, but on the length of the string.

2. Formalizing String Operations and the Proof Template

To prove properties of string operations, we must first define them with the same mathematical precision we used for strings themselves. Our intuitive understanding of "length," "concatenation," and "reversal" is a good guide, but for formal proofs, we need recursive definitions that mirror the recursive definition of a string ( $w = ϵ$ or $w = a x$ ).

The following resource provides these crucial definitions and lays out a "boilerplate" structure for writing inductive proofs about strings.

1 Strings

This document from Jeff Erickson's course at the University of Illinois provides excellent, clear, recursive definitions for string operations and a template for inductive proofs on strings.

Please read sections 1.2 ('Two Recursive Functions') and 1.3 ('Induction on Strings'). Pay close attention to the recursive definitions of length (|w|) and concatenation (w • z). Then, carefully study the boilerplate structure for string-induction proofs. This template is the key tool for this lesson.

Key Takeaways from the Reading

Let's summarize the essential definitions and the proof structure.

Recursive Definitions:

Length of a string w (|w|):
- If $w = ϵ$ , then $∣ w ∣ = 0$ .
- If $w = a x$ (where a is a symbol and x is a string), then $∣ w ∣ = 1 + ∣ x ∣$ .
Concatenation of strings w and z (w • z):
- If $w = ϵ$ , then $w \cdot z = z$ .
- If $w = a x$ , then $w \cdot z = a \cdot (x \cdot z)$ .
Reversal of a string w (w^R):
- If $w = ϵ$ , then $w^{R} = ϵ$ .
- If $w = a x$ , then $w^{R} = x^{R} \cdot a$ . (Notice how the first symbol a moves to the end).

The Induction Proof Template for Strings:

To prove a property $P (w)$ holds for all strings $w \in Σ^{*}$ :

Let $w$ be an arbitrary string.
Inductive Hypothesis (IH): Assume that for every string $x$ that is shorter than $w$ (i.e., $∣ x ∣ < ∣ w ∣$ ), the property $P (x)$ is true.
Base Case: Prove $P (ϵ)$ . Show the property holds for the empty string. (This is the case where $w = ϵ$ ).
Inductive Step: Prove $P (w)$ for $w \neq = ϵ$ . To do this:
- Write $w$ as $a x$ , where a is the first symbol and x is the rest of the string.
- By definition, $∣ x ∣ = ∣ w ∣ - 1$ , so the inductive hypothesis applies to x.
- Use the fact that $P (x)$ is true to show that $P (w)$ must also be true.

This structure provides a rigorous, step-by-step method for constructing proofs.

3. Proving Properties of String Operations

Now, let's use this template to prove some fundamental properties. We will work through proofs for properties involving length, reversal, and concatenation. The following resource contains clear, worked-out solutions for exactly these types of problems. We will study them together.

Solution: Discussion 01a

These solution notes provide detailed inductive proofs for several key properties of string reversal. We will analyze these proofs to see the template in action.

Start by reading the proofs for problems 1, 2, and 3. Don't just skim them; try to follow each step and see how it uses the definitions or the inductive hypothesis. We will break them down right after.

Proof 1: The length of a reversed string (`|w^R| = |w|`)

This property seems obvious, but proving it formally demonstrates the mechanics. Let's analyze the proof from the resource.

Proposition: For any string $w$ , $∣ w^{R} ∣ = ∣ w ∣$ .
Base Case: Let $w = ϵ$ .
- By definition of reversal, $w^{R} = ϵ^{R} = ϵ$ .
- By definition of length, $∣ w^{R} ∣ = ∣ ϵ ∣ = 0$ .
- Also by definition, $∣ w ∣ = ∣ ϵ ∣ = 0$ .
- So, $∣ w^{R} ∣ = ∣ w ∣$ holds for the base case.
Inductive Step: Let $w = a x$ , where $∣ x ∣ < ∣ w ∣$ .
- Inductive Hypothesis (IH): Assume $∣ x^{R} ∣ = ∣ x ∣$ .
- We want to prove $∣ w^{R} ∣ = ∣ w ∣$ . Let's start with the left side and transform it into the right side. $∣ w^{R} ∣ = ∣ (a x)^{R} ∣ = ∣ x^{R} \cdot a ∣ = ∣ x^{R} ∣ + ∣ a ∣ = ∣ x ∣ + ∣ a ∣ = ∣ x ∣ + 1 = ∣ a x ∣ = ∣ w ∣ (By definition of w) (By definition of reversal) (Using the property ∣ uv ∣ = ∣ u ∣ + ∣ v ∣^{*}) (By the Inductive Hypothesis) (A single symbol has length 1) (By definition of length) (By definition of w)$
- The proof holds.

(*Note: The property $∣ u \cdot v ∣ = ∣ u ∣ + ∣ v ∣$ is itself proven by induction. In a fully rigorous context, we would prove that first. Resource LINK, Lemma 1.2, contains that proof.)

Proof 2: Reversal of Concatenation (`(wz)^R = z^R w^R`)

This is often called the "socks and shoes" property: to reverse the action of putting on socks then shoes, you must first take off the shoes, then the socks.

Proposition: For any strings $w, z$ , $(w z)^{R} = z^{R} w^{R}$ .
Induction is on w. We let z be an arbitrary, fixed string.
Base Case: Let $w = ϵ$ .
- LHS: $(ϵz)^{R} = (z)^{R} = z^{R}$ .
- RHS: $z^{R} ϵ^{R} = z^{R} ϵ = z^{R}$ .
- LHS = RHS. The base case holds.
Inductive Step: Let $w = a x$ , where $∣ x ∣ < ∣ w ∣$ .
- Inductive Hypothesis (IH): Assume $(x z)^{R} = z^{R} x^{R}$ .
- We want to prove $((a x) z)^{R} = z^{R} (a x)^{R}$ . $((a x) z)^{R} = (a (x z))^{R} = (x z)^{R} \cdot a = (z^{R} x^{R}) \cdot a = z^{R} (x^{R} a) = z^{R} (a x)^{R} (By def. of concatenation) (By def. of reversal) (By the Inductive Hypothesis) (Concatenation is associative^{*}) (By def. of reversal)$
- The proof holds.

(*Associativity, $(uv) p = u (v p)$ , is also proven by induction. See LINK, Lemma 1.3.)

Test your understanding!

Using the template and the properties we just proved, try to outline a proof for (w^R)^R = w.

What is the base case?
For the inductive step, assume $w = a x$ . What is the inductive hypothesis?
How would you start the chain of equalities for the inductive step? (Hint: start with $((a x)^{R})^{R}$ and apply the definitions).

Show answer

Base Case: Let $w = ϵ$ . Then $(w^{R})^{R} = (ϵ^{R})^{R} = (ϵ)^{R} = ϵ = w$ . The base case holds.
Inductive Hypothesis: For $w = a x$ , the IH is that the property holds for the shorter string x. So, we assume (x^R)^R = x.
Inductive Step chain:
$(w^{R})^{R} = ((a x)^{R})^{R} = (x^{R} a)^{R} = a^{R} (x^{R})^{R} = a (x^{R})^{R} = a x = w (Substitute w = a x) (By definition of reversal) (Using the ’socks and shoes’ property we just proved) (Reversal of a single symbol is itself) (By the Inductive Hypothesis) (By definition of w)$

Conclusion

In this lesson, we made the important transition from simply defining concepts to formally proving their properties. This is a significant step up in mathematical maturity and is central to the theory of computation.

Here are the key takeaways:

Recursive Definitions: To formally reason about string operations like length, concatenation, and reversal, we need precise, recursive definitions.
Mathematical Induction on Strings: This is our primary tool for proving properties that hold for all strings. The proof structure involves a base case ( $ϵ$ ) and an inductive step (showing if it's true for x, it's true for ax).
Key Properties Proved: We analyzed proofs for several fundamental properties, including |w^R| = |w| and (wz)^R = z^R w^R.

You have now built a solid foundation in the formal preliminaries. You can define the objects of study (alphabets, strings, languages) and you have the primary tool for reasoning about them (induction).

In the next lesson, we will move back to the level of languages. We will explore how to build new, more complex languages from existing ones using familiar set operations like union, intersection, and complement, as well as language-specific operations like language concatenation and the Kleene star.

Recommended resources