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.


This needs considerable tedious hard slog to complete it.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Finish}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.



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$.


This needs considerable tedious hard slog to complete it.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Finish}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.


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

Retrieved from "https://proofwiki.org/w/index.php?title=Equivalence_of_Definitions_of_Balanced_String&oldid=614630"