Show that every string of balanced parentheses is the string of parentheses in s

Question

Show that every string of balanced parentheses is the string of parentheses in some arithmetic expression. Hint: Use a proof by induction on the number of times the recursive rule of the definition of “balanced parentheses” is used to construct the given string of balanced parentheses.

I know that if the arithmetic expression contains no parentheses, then recursive definition is applied 0 times and that the expression contains only an operand and potnentialy some number of operators. I need to know both the basis case and the inductive step for this problem. Any help is apperciated!

Explanation / Answer

Infix expression:

                        A + B * ( C * D – E / F ) / G – H

Prefix expression:

                        - + A / * B - * C D / E F G H

Postfix expression:
                        A B C D * E F / - * G / + H -

Statement:

Every string of balanced parentheses is the string of parentheses in some arithmetic expression.

Prove:

The strings of balanced parentheses can be defined in a string w over alphabet {), (} is balanced if:

This can be prove by induction on the length of the string and that definitions define the same class of strings. Use the notation 1-balanced and 2-balanced to describe strings that are balanced by definition 1 and 2 respectively.

By the induction step, any string of length k is 1-balanced if it is 2-balanced. So, prove that this is also true for any string w of length k + 2.

|u| < |w|: Since appending v to u must produce the 1-balanced string w, we can show that v must satisfy both rules of definition 1, and is therefore also 1-balanced. Since u and v both have length _ k and both are 1-balanced, both are also 2-balanced, by the induction hypothesis. Applying the second rule of definition 2, uv = w must also be 2-balanced.

|u| = |w|: Let xsy = u, where |x| = |y| = 1. Since u is 1-balanced, x must be ( by the prefix rule. Furthermore, y must be ), since otherwise xs would have more )’s than (’s, violating the prefix rule for u. But now we can prove that s is 1-balanced. We know s must have equal numbers of (’s and )’s, because we removed one of each from u, which was 1-balanced.

We also know that it has no prefix with more )’s than (’s.

This can be proving by contradiction. First find the shortest such prefix z.

By construction, it must have exactly one more ) than (. But the string xz would then have been a 1- balanced prefix of w, and we know that no such prefix exists, so this is a contradiction.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.