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 \({\bf{S}} \to {\bf{A,A}} \to {\bf{AB,A}} \to {\bf{B,B}} \to {\bf{A,}}\)and \({\bf{B}} \to {\bf{(),S}} \to {\bf{\lambda }}\)

Construct the derivation trees of these strings.

\({\bf{a)}}\)\({\bf{(())}}\)

\({\bf{b)}}\)\({\bf{()(())}}\)

\({\bf{c)}}\)\({\bf{((()()))}}\)

Short answer

\({\bf{a)}}\)The constructed derivative of the given string is \({\bf{(())}}\).

\({\bf{b)}}\)The constructed derivative of the given string is \({\bf{()(())}}\).

\({\bf{c)}}\)The constructed derivative of the given string is \({\bf{((()()))}}\).

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:

\(\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 production rule

(a)

It is given that \({\bf{(())}}\).

There is only one production with the starting symbol \({\bf{S}}\) with \({\bf{\lambda }}\), thus it needs to use this production first.

\({\bf{S}} \to {\bf{A}}\)

Since the expression \({\bf{(())}}\) contains only one set of outer brackets, you next need to use the following production rule:

\({\bf{A}} \to {\bf{B}}\)

Next, add the first set of outer brackets. Since there still need to be some brackets added within this set of brackets, it needs to use the following rule:

\({\bf{B}} \to {\bf{(A)}}\)

Within the outer set of brackets is only one pair of brackets and thus you then need to use the following production on the element \({\bf{A}}\) in \(\left( {\bf{A}} \right)\).

\({\bf{A}} \to {\bf{B}}\)

Constructing the tree

Finally, it needs to add the final set of brackets by replacing \({\bf{B}}\) by \({\bf{()}}\) in \(\left( {\bf{B}} \right)\) to obtain \({\bf{(())}}\).

\({\bf{B}} \to {\bf{()}}\)

Then obtain the derivation tree by making \({\bf{S}}\) the root of the tree and by adding \({\bf{x}}\) as a child of \({\bf{y}}\) per production \({\bf{x}} \to {\bf{y}}\) that was used in the derivation above.

Hence, it gives \({\bf{(())}}\).

Using the production rule

(b)

It is given that \({\bf{()(())}}\).

There is only one production with the starting symbol \({\bf{S}}\) with \({\bf{\lambda }}\), thus it needs to use this production first.

\({\bf{S}} \to {\bf{A}}\)

Since the expression \({\bf{()(())}}\) contains a concatenation of two groups of brackets, next need to use the following production rule:

\({\bf{A}} \to {\bf{AB}}\)

Then add the first group of brackets \({\bf{()}}\) in \({\bf{()(())}}\) by using the following rule (such that you obtain \({\bf{()B}}\)):

\({\bf{A}} \to {\bf{()}}\)

Next, add the first set of outer brackets in the second group of brackets in \({\bf{()(())}}\).

Since there still need to be some brackets added within this set of brackets, it needs to use the following rule (such that you obtain \({\bf{()}}\left( {\bf{A}} \right)\)).

\({\bf{B}} \to {\bf{(A)}}\)

The remaining \({\bf{A}}\) in \({\bf{()}}\left( {\bf{A}} \right)\) still contains only one set of brackets and thus you then need to use the following production on the element \({\bf{A}}\) in \({\bf{()}}\left( {\bf{A}} \right)\).

\({\bf{A}} \to {\bf{B}}\)

Constructing the tree

Finally, it needs to add the final set of brackets by replacing \({\bf{B}}\) by \({\bf{()}}\) in \({\bf{()}}\left( {\bf{B}} \right)\) to obtain \({\bf{()(())}}\).

\({\bf{B}} \to {\bf{()}}\)

Then obtain the derivation tree by making \({\bf{S}}\) the root of the tree and by adding \({\bf{x}}\) as a child of \({\bf{y}}\) per production \({\bf{x}} \to {\bf{y}}\) that was used in the derivation above. Hence, it gets \({\bf{()(())}}\).

Using the production rule

(c)

It is given that \({\bf{((()()))}}\).

There is only one production with the starting symbol \({\bf{S}}\) with \({\bf{\lambda }}\), thus it needs to use this production first.

\({\bf{S}} \to {\bf{A}}\)

Since the expression \({\bf{(())}}\) contains only one set of outer brackets, next it needs to use the following production rule:

\({\bf{A}} \to {\bf{B}}\)

Next, add the first set of outer brackets. Since there still need to be some brackets added within this set of brackets, it needs to use the following rule:

\({\bf{B}} \to {\bf{(A)}}\)

Within the outer set of brackets is one pair of outer brackets and thus it needs to use the following production on the element \({\bf{A}}\) in \(\left( {\bf{A}} \right)\).

\({\bf{A}} \to {\bf{B}}\)

Next, it adds the second set of outer brackets. Since there still need to be some brackets added within this set of brackets, it needs to use the following rule such that it obtains \(\left( {\left( {\bf{A}} \right)} \right)\):

\({\bf{B}} \to {\bf{(A)}}\)

Now, it needs the concatenation of two sets of brackets for \({\bf{A}}\) in \(\left( {\left( {\bf{A}} \right)} \right)\) and thus it uses the following production rule:

\({\bf{A}} \to {\bf{AB}}\)

Constructing the tree

It obtained \(\left( {{\bf{A B}}} \right)\) where \({\bf{A}}\) and \({\bf{B}}\) both need to be \({\bf{()}}\) , which is done by using the production rule \({\bf{A}} \to {\bf{B}}\) and using the production rule \({\bf{B}} \to {\bf{()}}\) twice.

\(\begin{array}{l}{\bf{A}} \to {\bf{B}}\\{\bf{B}} \to {\bf{()}}\\{\bf{B}} \to {\bf{()}}\end{array}\)

Then it obtains the derivation tree by making \({\bf{S}}\) the root of the tree and by adding \({\bf{x}}\) as a child of \({\bf{y}}\) per production \({\bf{x}} \to {\bf{y}}\) that was used in the derivation above. Hence, it gets \({\bf{(()()))}}\).