Definition:Balanced String/Definition 2

Definition

Let $S$ be a string in an alphabet containing brackets.

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

Also see

• Equivalence of Definitions of Balanced String

Sources

• 1979: John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation ... (previous) ... (next): Chapter $1$: Preliminaries: Exercises: $1.4$