snippetModerate
How do I write a proof using induction on the length of the input string?
Viewed 0 times
thelengthwriteinputusinghowstringproofinduction
Problem
In my Computing Theory course, a lot of our problems involve using induction on the length of the input string to prove statements about finite automata. I understand mathematical induction, however when strings come into play I get real tripped up. I'd really appreciate it if someone would go through the process of making such a proof step by step.
Here's an example problem (Exercise 2.2.10 from Hopcroft and Ullman 3rd Edition):
Consider the DFA with the following transition table:
0 1
________
-> A | A B
*B | B A
Informally describe the language accepted by this DFA, and prove by induction on the length of an input string that your description is correct.
This is an answered problem in the book, so I'm not looking for someone to do my homework. I just need someone to explain it to me straight.
Book's Answer:
(taken from here)
The automaton tells whether the number of 1's seen is even (state A) or odd (state B), accepting in the latter case. It is an easy induction on |w| to show that dh(A,w) = A if and only if w has an even number of 1's.
Basis: |w| = 0. Then w, the empty string surely has an even number of 1's, namely zero 1's, and δ-hat(A,w) = A.
Induction: Assume the statement for strings shorter than w. Then w = za, where a is either 0 or 1.
-
Case 1: a = 0. If w has an even number of 1's, so does z. By the inductive hypothesis, δ-hat(A,z) = A. The transitions of the DFA tell us δ-hat(A,w) = A. If w has an odd number of 1's, then so does z. By the inductive hypothesis, δ-hat(A,z) = B, and the transitions of the DFA tell us δ-hat(A,w) = B. Thus, in this case, δ-hat(A,w) = A if and only if w has an even number of 1's.
-
Case 2: a = 1. If w has an even number of 1's, then z has an odd number of 1's. By the inductive hypothesis, δ-hat(A,z) = B. The transitions of the DFA tell us δ-hat(A,w) = A. If w has an odd number of 1's, then z has an even number of 1's. By the inductive hypothesis, δ-hat(
Here's an example problem (Exercise 2.2.10 from Hopcroft and Ullman 3rd Edition):
Consider the DFA with the following transition table:
0 1
________
-> A | A B
*B | B A
Informally describe the language accepted by this DFA, and prove by induction on the length of an input string that your description is correct.
This is an answered problem in the book, so I'm not looking for someone to do my homework. I just need someone to explain it to me straight.
Book's Answer:
(taken from here)
The automaton tells whether the number of 1's seen is even (state A) or odd (state B), accepting in the latter case. It is an easy induction on |w| to show that dh(A,w) = A if and only if w has an even number of 1's.
Basis: |w| = 0. Then w, the empty string surely has an even number of 1's, namely zero 1's, and δ-hat(A,w) = A.
Induction: Assume the statement for strings shorter than w. Then w = za, where a is either 0 or 1.
-
Case 1: a = 0. If w has an even number of 1's, so does z. By the inductive hypothesis, δ-hat(A,z) = A. The transitions of the DFA tell us δ-hat(A,w) = A. If w has an odd number of 1's, then so does z. By the inductive hypothesis, δ-hat(A,z) = B, and the transitions of the DFA tell us δ-hat(A,w) = B. Thus, in this case, δ-hat(A,w) = A if and only if w has an even number of 1's.
-
Case 2: a = 1. If w has an even number of 1's, then z has an odd number of 1's. By the inductive hypothesis, δ-hat(A,z) = B. The transitions of the DFA tell us δ-hat(A,w) = A. If w has an odd number of 1's, then z has an even number of 1's. By the inductive hypothesis, δ-hat(
Solution
As it is unclear where your problem lies, I'll start at the very beginning.
Mathematical induction works like the game of Chinese whispers (in the ideal case, i.e. all communication is lossless) or (perfectly set up) dominoes: you start somewhere and show that your every next step does not break anything, assuming nothing has been broken till then.
More formally, every induction proof consists of three basic elements:
Of course, the step has to be tuned such that it covers the whole base set (in the limit).
Important note: people who are confident of their induction skills often gloss over the anchor and leave the hypothesis implicit. While this is fine when presenting your work to an expert audience (e.g. a paper), this is not recommended when doing proofs yourself, especially as a beginner. Write down everything.
Consider a simple example over $(\mathbb{N},\leq)$; we want to show that $\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$ holds for all $n \in \mathbb{N}$.
-
Step: For $n+1$, compute the sum:
$\qquad \displaystyle \sum_{i=0}^{n+1} i = (n+1) + \sum_{i=0}^{n} i \overset{\text{IH}}{=} n+1 + \frac{n(n+1)}{2} = \frac{(n+2)(n+1)}{2}$
So the identity holds for $n+1$. (We note that we only needed a tiny part of the hypothesis, namely for $k=n$. That often happens.)
The inductive principle now assures us that the claim indeed holds: we have directly shown it for $0$. The step says, if it holds for $0$, it also holds for $1$; if it holds for $1$, it also holds for $2$; and so on.
Let's have a look at another example, this time on $(2^\mathbb{N}, \subseteq)$. The claim we want to prove is: for every finite subset $A$ of $\mathbb{N}$, the size of the power set $2^A$ of $A$ is $2^{|A|}$³. We perform our induction over $(\mathbb{N}, \leq)$, again, namely over the size of subsets $A$.
-
Step: Let $B \subseteq \mathbb{N}$ arbitrary⁴ of size $n+1$, and let $b \in B$ arbitrary (such $b$ exists as $n+1 > 0$). Now the hypothesis applies to $B \setminus \{b\}$ and thus $|2^{B \setminus \{b\}}| = 2^n$. Since
$\qquad \displaystyle 2^B = 2^{B \setminus \{b\}} \cup \{ A \cup \{b\}\mid A \in 2^{B \setminus \{b\}} \}$,
we have indeed that $|2^{B}| = 2 \cdot |2^{B \setminus \{b\}}| = 2 \cdot 2^n = 2^{n+1}$ as claimed.
Again, by induction the claim is proven.
Now, for your problem can use a common trick: strengthening the statement. If you formulate your claim as "the automaton accepts all words with an odd number of ones", you get an induction hypothesis like "among all words of length $n$, exactly those with an odd number of ones are accepted by the automaton". This won't lead you anywhere since we don't know anything about how many ones are contained in which part of a given (accepted) word; the hypothesis does not apply on whatever you cut away of your arbitrarily selected word.
Therefore, you want to formulate a stronger claim: "The automaton is in state $B$ if and only if the consumed part of the input contained an odd number of ones", and show this one. Note that it implies the former claim.
The principle of induction implies that the claim indeed holds.
Mathematical induction works like the game of Chinese whispers (in the ideal case, i.e. all communication is lossless) or (perfectly set up) dominoes: you start somewhere and show that your every next step does not break anything, assuming nothing has been broken till then.
More formally, every induction proof consists of three basic elements:
- Induction anchor, also base case: you show for small cases¹ that the claim holds.
- Induction hypothesis: you assume that the claim holds for a certain subset of the set you want to prove something about.
- Inductive step: Using the hypothesis, you show that the claim holds for more elements.
Of course, the step has to be tuned such that it covers the whole base set (in the limit).
Important note: people who are confident of their induction skills often gloss over the anchor and leave the hypothesis implicit. While this is fine when presenting your work to an expert audience (e.g. a paper), this is not recommended when doing proofs yourself, especially as a beginner. Write down everything.
Consider a simple example over $(\mathbb{N},\leq)$; we want to show that $\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$ holds for all $n \in \mathbb{N}$.
- Anchor: For $n=0$, $\sum_{i=0}^{n} i = 0 = \frac{n(n+1)}{2}$ clearly holds.
- Hypothesis: Assume that $\sum_{i=0}^{k} i = \frac{k(k+1)}{2}$ holds for an arbitrary, but fixed² $n \in \mathbb{N}$.
-
Step: For $n+1$, compute the sum:
$\qquad \displaystyle \sum_{i=0}^{n+1} i = (n+1) + \sum_{i=0}^{n} i \overset{\text{IH}}{=} n+1 + \frac{n(n+1)}{2} = \frac{(n+2)(n+1)}{2}$
So the identity holds for $n+1$. (We note that we only needed a tiny part of the hypothesis, namely for $k=n$. That often happens.)
The inductive principle now assures us that the claim indeed holds: we have directly shown it for $0$. The step says, if it holds for $0$, it also holds for $1$; if it holds for $1$, it also holds for $2$; and so on.
Let's have a look at another example, this time on $(2^\mathbb{N}, \subseteq)$. The claim we want to prove is: for every finite subset $A$ of $\mathbb{N}$, the size of the power set $2^A$ of $A$ is $2^{|A|}$³. We perform our induction over $(\mathbb{N}, \leq)$, again, namely over the size of subsets $A$.
- Anchor: Consider the (only) set of size $0$, the empty set. Clearly, $2^\emptyset = \{\emptyset\}$ and therefore $|2^\emptyset| = 1 = 2^0$ as claimed.
- Hypothesis: Assume that for all sets $A \subseteq \mathbb{N}$ with $|A| \leq n$ with some arbitrary, but fixed $n \in \mathbb{N}$, we have $|2^A| = 2^{|A|}$.
-
Step: Let $B \subseteq \mathbb{N}$ arbitrary⁴ of size $n+1$, and let $b \in B$ arbitrary (such $b$ exists as $n+1 > 0$). Now the hypothesis applies to $B \setminus \{b\}$ and thus $|2^{B \setminus \{b\}}| = 2^n$. Since
$\qquad \displaystyle 2^B = 2^{B \setminus \{b\}} \cup \{ A \cup \{b\}\mid A \in 2^{B \setminus \{b\}} \}$,
we have indeed that $|2^{B}| = 2 \cdot |2^{B \setminus \{b\}}| = 2 \cdot 2^n = 2^{n+1}$ as claimed.
Again, by induction the claim is proven.
Now, for your problem can use a common trick: strengthening the statement. If you formulate your claim as "the automaton accepts all words with an odd number of ones", you get an induction hypothesis like "among all words of length $n$, exactly those with an odd number of ones are accepted by the automaton". This won't lead you anywhere since we don't know anything about how many ones are contained in which part of a given (accepted) word; the hypothesis does not apply on whatever you cut away of your arbitrarily selected word.
Therefore, you want to formulate a stronger claim: "The automaton is in state $B$ if and only if the consumed part of the input contained an odd number of ones", and show this one. Note that it implies the former claim.
- Anchor: After processing the only string of length zero, $\varepsilon$, the automaton is clearly in state $A$ as claimed.
- Hypothesis: Assume that claim holds for input fragments of length up to $n$ which is chosen arbitrarily, but fixed.
- Step: Consider an arbitrary word $w \in \{0,1\}^{n+1}$. There are two cases.
- $w$ contains an even number of ones. There are two cases for the last symbol.
- $w_n = 0$: In this case, $w' = w_1 \dots w_{n-1}$ contains an even number of ones. By induction hypothesis, the automaton is in state $A$ after consuming $w'$. Consuming $w_n = 0$ causes the automaton to stay in state $A$, as claimed.
- $w_n = 1$: In this case, $w' = w_1 \dots w_{n-1}$ contains an odd number of ones. By induction hypothesis, the automaton is in state $B$ after consuming $w'$. Consuming $w_n = 1$ causes the automaton to switch to state $A$, as claimed.
- $w$ contains an odd number of ones. Similar to case 1.
The principle of induction implies that the claim indeed holds.
- You perform induction along some partial order; the anchor needs to cover all minimal elements, and sometimes more (depending on the st
Context
StackExchange Computer Science Q#4905, answer score: 17
Revisions (0)
No revisions yet.