Question

Let \({\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)\) be the context-free grammar with \({\bf{V = }}\left\{ {\left( {\bf{,}} \right){\bf{S,A,B}}} \right\}{\bf{, T = }}\left\{ {\left( {\bf{,}} \right)} \right\}\) starting symbol \({\bf{S}}\), and productions

Show that \({\bf{L}}\left( {\bf{G}} \right)\) is the set of all balanced strings of parentheses, defined in the preamble to Supplementary Exercise \(55\) in Chapter \(4\).

Short answer

\({\bf{L}}\left( {\bf{G}} \right){\bf{ = }}\) It is the set of balanced strings of parentheses.

Step-by-step solution

Definition

In formal language theory, a context-free grammar is a formal grammar whose production rules are of the form\({\bf{A}}\)to\({\bf{\alpha }}\)with a single nonterminal symbol, and\({\bf{\alpha }}\)a string of terminals and/or non-terminals.

Given: \({\bf{B}}\) is the set of all balanced strings

\({\bf{\lambda }} \in {\bf{B}}\)

\({\bf{(x)}} \in {\bf{B}}\)if \({\bf{x}} \in {\bf{B}}\)

\({\bf{xy}} \in {\bf{B}}\)if \({\bf{xy}} \in {\bf{B}}\)

\(\begin{array}{l}{\bf{G = (V,T,S,P)}}\\{\bf{V = \{ (,),S,A,B\} }}\\{\bf{T}} = {\bf{\{ (,)\} }}\\{\bf{S}} \to {\bf{A}}\\{\bf{A}} \to {\bf{AB}}\\{\bf{A}} \to {\bf{B}}\\{\bf{B}} \to {\bf{(A)}}\\{\bf{B}} \to {\bf{()}}\\{\bf{S}} \to {\bf{\lambda }}\end{array}\)

Using the strong induction

To proof: \({\bf{L}}\left( {\bf{G}} \right){\bf{ = }}\) Set of all balanced strings of parentheses.

PROOF BY STRONG INDUCTION

Assume \({\bf{P(n)}}\) be the statement "String \({\bf{x}}\) which is produced by \({\bf{G}}\) is a balanced string when \({\bf{x}}\) is a balanced string with \({\bf{2n}}''\).

Base step \({\bf{n = 0}}\).

The only string of length \({\bf{2 n = 2}}\left( {\bf{0}} \right){\bf{ = 0}}\) is the empty string \({\bf{\lambda }}\).

Note that \({\bf{\lambda }}\) is generated by \({\bf{G}}\) due to the production rule \({\bf{S}} \to {\bf{\lambda }}\). Moreover, \({\bf{\lambda }}\) is also a balanced string as \({\bf{\lambda }} \in {\bf{B}}\). Thus \({\bf{P}}\left( {\bf{0}} \right)\) is true.

Inductive step Let \({\bf{P(0),P(1), \ldots ,P(k)}}\) be true, thus the string \({\bf{x}}\) that is produced by \({\bf{G}}\) is a balanced string when \({\bf{x}}\) is a balanced string with length \({\bf{2i}}\) for \({\bf{i = 0,1,2, \ldots ,k}}\).

Proving \({\bf{P}}\left( {{\bf{k + 1}}} \right)\) is true

Let \({\bf{y}}\) be a string of length \({\bf{2}}\left( {{\bf{k + 1}}} \right){\bf{ = 2 k + 2}}\) that is produced by \({\bf{G}}\).\({\bf{y}}\) is then of the form \(\left( {\bf{x}} \right)\) or of the form \({\bf{a b}}\) (with \({\bf{x}}\), \({\bf{a}}\) and \({\bf{b}}\) strings that were produced by \({\bf{G}}\)).

If \({\bf{y}}\) is of the form \(\left( {\bf{x}} \right)\), then \({\bf{x}}\) is a string of length \({\bf{2k}}\). Since \({\bf{P(k)}}\) is true, \({\bf{x}}\) is a balanced string \({\bf{x}} \in {\bf{B}}\). Since \({\bf{x}} \in {\bf{B}}\) : \({\bf{(x)}} \in {\bf{B}}\) and thus \({\bf{y = }}\left( {\bf{x}} \right)\) is a balanced string.

If \({\bf{y}}\) is of the form \({\bf{a b}}\), then \({\bf{a}}\) is a string of length \({\bf{2i}}\) while \({\bf{b}}\) is a string of length \({\bf{2 k + 2 - 2 i = 2}}\left( {{\bf{k + 1 - i}}} \right)\). Since \({\bf{P(i)}}\) is true, \({\bf{a}}\) is a balanced string \({\bf{a}} \in {\bf{B}}\). Since \({\bf{P}}\left( {{\bf{k + 1 - i}}} \right)\) is true, \({\bf{b}}\) is a balanced string \({\bf{b}} \in {\bf{B}}\). Since \({\bf{a}} \in {\bf{B}}\) and \({\bf{b}} \in {\bf{B}}\):\({\bf{ab}} \in {\bf{B}}\) and thus \({\bf{y = ab}}\) is a balanced string.

Thus \({\bf{P}}\left( {{\bf{k + 1}}} \right)\) is true.

Conclusion by the principle of strong induction, \({\bf{P(n)}}\) is true for all nonnegative integers \({\bf{n}}\).

Therefore, \({\bf{L}}\left( {\bf{G}} \right){\bf{ = }}\) Set of all balanced strings of parentheses.