Question

let \({{\bf{G}}_{\bf{1}}}\) and \({{\bf{G}}_{\bf{2}}}\) be context-free grammars, generating the language\({\bf{L}}\left( {{{\bf{G}}_{\bf{1}}}} \right)\) and \({\bf{L}}\left( {{{\bf{G}}_{\bf{2}}}} \right)\), respectively. Show that there is a context-free grammar generating each of these sets.

a) \({\bf{L}}\left( {{{\bf{G}}_{\bf{1}}}} \right){\bf{UL}}\left( {{{\bf{G}}_{\bf{2}}}} \right)\)

b) \({\bf{L}}\left( {{{\bf{G}}_{\bf{1}}}} \right){\bf{L}}\left( {{{\bf{G}}_{\bf{2}}}} \right)\)

c) \({\bf{L}}{\left( {{{\bf{G}}_{\bf{1}}}} \right)^{\bf{*}}}\)

Short answer

a) Add S and productions \({\bf{S}} \to {{\bf{S}}_{\bf{1}}}\) and \({\bf{S}} \to {{\bf{S}}_{\bf{2}}}\).

b) Add S and production \({\bf{S}} \to {{\bf{S}}_{\bf{1}}}{{\bf{S}}_{\bf{2}}}\).

c) Add S and production S → λ and \({\bf{S}} \to {{\bf{S}}_{\bf{1}}}{\bf{S}}\).

Step-by-step solution

Types of Phrase-Structure Grammars Phrase-structure grammars.

(l)A type- 0 grammar has no restrictions on its production.

(II) A type-1 grammar can have productions of the form \({{\bf{W}}_{\bf{1}}} \to {{\bf{W}}_{\bf{2}}}\), where \({{\bf{W}}_{\bf{1}}} \to {\bf{lAr}}\). and \({{\bf{W}}_{\bf{2}}} \to {\bf{lWr}}\), where A is a non-terminal, I and r, are zero or more terminal or non-terminals and W is a non-empty string of terminal or non-terminals. It can also have the production Sàλ. as long as S does not appear on the right-hand side of any other production.

(III)A type- 2 grammar can have the productions only of the form \({{\bf{W}}_{\bf{1}}} \to {{\bf{W}}_{\bf{2}}}\), where \({{\bf{W}}_{\bf{1}}}\) is a single non-terminal.

(IV) A type- 3 grammar can have the productions only of the form \({{\bf{W}}_{\bf{1}}} \to {{\bf{W}}_{\bf{2}}}\) with \({{\bf{W}}_{\bf{1}}}{\bf{ = A}}\) and either \({{\bf{W}}_{\bf{2}}}{\bf{ = aB}}\) or \({{\bf{W}}_{\bf{2}}}{\bf{ = a}}\) where A and B are non-terminals and a is a terminal or with \({{\bf{W}}_{\bf{1}}}{\bf{ = S}}\) and \({{\bf{W}}_{\bf{2}}}{\bf{ = \lambda }}\).

Type 2 grammars are called context-free grammars because a nonterminal symbol that is the left side of a production can be replaced in a string whenever it occurs, no matter what else is in the string.

Firstly, it shall show that there is a context-free grammar generating \({\bf{L}}\left( {{{\bf{G}}_{\bf{1}}}} \right){\bf{UL}}\left( {{{\bf{G}}_{\bf{2}}}} \right)\) sets

(a)

Take two non-terminal symbols \({{\bf{G}}_{\bf{1}}}\) and \({{\bf{G}}_{\bf{2}}}\) which are of context free grammars.

Here, the start symbols are \({{\bf{S}}_{\bf{1}}}\) and \({{\bf{S}}_{\bf{2}}}\).

Let ‘S’ be the non-terminal symbol.

Let \({\bf{L}}\left( {{{\bf{G}}_{\bf{1}}}} \right)\) and \({\bf{L}}\left( {{{\bf{G}}_{\bf{2}}}} \right)\) be language generators for \({{\bf{G}}_{\bf{1}}}\) and \({{\bf{G}}_{\bf{2}}}\) respectively.

The language generated by the union contains all the strings generated by both the languages \({\bf{L}}\left( {{{\bf{G}}_{\bf{1}}}} \right)\) and \({\bf{L}}\left( {{{\bf{G}}_{\bf{2}}}} \right)\).

Here, apply the production rules to \({\bf{S}} \to {{\bf{S}}_{\bf{1}}}\) and \({\bf{S}} \to {{\bf{S}}_{\bf{2}}}\).

So, the productions rules for \({\bf{S}} \to {{\bf{S}}_{\bf{1}}}\) and \({\bf{S}} \to {{\bf{S}}_{\bf{2}}}\) are of type 2.

Thus, the language \({\bf{L}}\left( {{{\bf{G}}_{\bf{1}}}} \right){\bf{UL}}\left( {{{\bf{G}}_{\bf{2}}}} \right)\) is a context free language.

Therefore, the string\({\bf{L}}\left( {{{\bf{G}}_{\bf{1}}}} \right){\bf{UL}}\left( {{{\bf{G}}_{\bf{2}}}} \right)\)is a context-free grammar.

Now, we shall show that there is a context-free grammar generating \({\bf{L}}\left( {{{\bf{G}}_{\bf{1}}}} \right){\bf{L}}\left( {{{\bf{G}}_{\bf{2}}}} \right)\) sets.

(b)

The language generated by the product contains the strings generated by both the languages \({\bf{L}}\left( {{{\bf{G}}_{\bf{1}}}} \right),\,{\bf{L}}\left( {{{\bf{G}}_{\bf{2}}}} \right)\) and more strings.

Here, applies the production rule to \({\bf{S}} \to {{\bf{S}}_{\bf{1}}}{{\bf{S}}_{\bf{2}}}\).

So, the productions rule for \({\bf{S}} \to {{\bf{S}}_{\bf{1}}}{{\bf{S}}_{\bf{2}}}\) is of type 2. Thus, the language \({\bf{L}}\left( {{{\bf{G}}_{\bf{1}}}} \right){\bf{L}}\left( {{{\bf{G}}_{\bf{2}}}} \right)\) is a context free language.

In the above rule, the left side of production is replaced by the string, \({{\bf{S}}_{\bf{1}}}{{\bf{S}}_{\bf{2}}}\).

So, this production comes under type 2 grammars.

Now, we shall show that there is a context-free grammar generating \({\bf{L}}{\left( {{{\bf{G}}_{\bf{1}}}} \right)^{\bf{*}}}\) sets.

(c)

The language \({\bf{L}}{\left( {{{\bf{G}}_{\bf{1}}}} \right)^{\bf{*}}}\) contains all the strings of the language \({\bf{L}}\left( {{{\bf{G}}_{\bf{1}}}} \right)\). The language \({\bf{L}}{\left( {{{\bf{G}}_{\bf{1}}}} \right)^{\bf{*}}}\) contains the strings, which are repetitions of the strings generated by the language \({\bf{L}}\left( {{{\bf{G}}_{\bf{1}}}} \right)\).

First, add a non-terminal string S to the set of all non-terminal strings.

So, the grammar contains the production rule of \({{\bf{G}}_{\bf{1}}}\) and along with it, it also contains S \(\to\) λ and \({\bf{S}} \to {{\bf{S}}_{\bf{1}}}{\bf{S}}\).

Apply the production rule to \({\bf{S}} \to {{\bf{S}}_{\bf{1}}}{\bf{S}}\). A string of concatenation is formed. To obtained string apply the production rule Sàλ to get the string generated by the language \({\bf{L}}{\left( {{{\bf{G}}_{\bf{1}}}} \right)^{\bf{*}}}\). The language generated by \({\bf{L}}{\left( {{{\bf{G}}_{\bf{1}}}} \right)^{\bf{*}}}\) is obtained by applying the production rules \({\bf{S}} \to {{\bf{S}}_{\bf{1}}}{\bf{S}}\) to \({\bf{L}}\left( {{{\bf{G}}_{\bf{1}}}} \right)\).

So, this production comes under type 2 grammar.

Therefore, the language\({\bf{L}}{\left( {{{\bf{G}}_{\bf{1}}}} \right)^{\bf{*}}}\)is a context free language.