Equivalence of Definitions of Balanced String

From ProofWiki
Jump to navigation Jump to search

Theorem

The following definitions of the concept of Balanced String are equivalent:

Definition 1

$S$ is said to be balanced if and only if:

$(1): \quad S$ contains equally many left and right brackets.
$(2): \quad$ Every prefix of $S$ contains at least as many left brackets as it does right brackets.

Definition 2

$S$ is said to be balanced if and only if it satisfies the following:

$(1): \quad$ The null string $\epsilon$ is a balanced string.
$(2): \quad$ If $x$ is a symbol that is specifically not a bracket, then the string consisting just of $x$ is a balanced string.
$(3): \quad$ If $S$ is a balanced string, then $\paren S$ is a balanced string.
$(4): \quad$ If $S$ and $T$ are balanced strings, then $S T$ is a balanced string.
$(5): \quad$ Nothing is a balanced string unless it has been created by one of the rules $(1)$ to $(4)$.


Proof

The proof proceeds by strong induction on the length of a string.

For all $n \in \N$, let $\map P n$ be the proposition:

Every balanced string $S_n$ of length $n$ is a balanced string by definition $1$ if and only if it been generated by definition $2$.


Basis for the Induction

$\map P 0$ is the case:

Every balanced string $S_0$ of length $0$ is a balanced string by definition $1$ if and only if it been generated by definition $2$.

By definition $2$ of a balanced string:

$(1): \quad$ The null string $\epsilon$ is a balanced string.

This is the only string of length $0$.

$\epsilon$ is seen vacuously to be a balanced string by definition $1$.

Thus $\map P 0$ is seen to hold.


$\map P 1$ is the case:

Every balanced string $S_1$ of length $n$ is a balanced string by definition $1$ if and only if it been generated by definition $2$.

Let $a$ be an arbitrary symbol.




We use $\map P 0$ and $\map P 1$ together to form the basis for the induction.


Induction Hypothesis

Now it needs to be shown that if $\map P j$ is true, for all $j$ such that $0 \le j \le k$ and $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.


This is the induction hypothesis:

Every balanced string $S_j$ of length $j$ such that $j \le k$ is a balanced string by definition $1$ if and only if it been generated by definition $2$.


from which it is to be shown that:

Every balanced string $S_{k + 1}$ of length $k + 1$ is a balanced string by definition $1$ if and only if it been generated by definition $2$.


Induction Step

This is the induction step:

Let $x$ be a balanced string of length $k - 1$ according to either definition $1$ or definition $2$.

By the induction hypothesis, $x$ is therefore a balanced string by both definition $1$ and definition $2$.



Thus we have shown that for all $k \in \N$, if $\sqbrk y$ reads the same backwards as it does forwards, then it has been created by one of the rules $(1)$, $(2)$ or $(3)$.


So $\paren {\forall j: 0 \le j \le k: \map P j} \implies \map P {k + 1}$ and the result follows by the Second Principle of Mathematical Induction.


Therefore:

For all $n \in \N$: every balanced string $S_n$ of length $n$ is a balanced string by definition $1$ if and only if it been generated by definition $2$.

$\blacksquare$


Sources