Question

Let V = {S, A, B, a, b} and T = {a, b}. Find the language generated by the grammar (V, T, S, P) when theset P of productions consists of

\(\begin{array}{*{20}{l}}{{\bf{a) S }} \to {\bf{ AB, A }} \to {\bf{ ab, B }} \to {\bf{ bb}}{\bf{.}}}\\{{\bf{b) S }} \to {\bf{ AB, S }} \to {\bf{ aA, A }} \to {\bf{ a, B }} \to {\bf{ ba}}{\bf{.}}}\\{{\bf{c) S }} \to {\bf{ AB, S }} \to {\bf{ AA, A }} \to {\bf{ aB, A }} \to {\bf{ ab, B }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{d) S }} \to {\bf{ AA, S }} \to {\bf{ B, A }} \to {\bf{ aaA, A }} \to {\bf{ aa, B }} \to {\bf{ bB, B }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{e) S }} \to {\bf{ AB, A }} \to {\bf{ aAb, B }} \to {\bf{ bBa, A }} \to {\bf{ \lambda , B }} \to {\bf{ \lambda }}{\bf{.}}}\end{array}\)

Short answer

(a) The result is\({\bf{\{ abbb\} }}\)

(b) The result is\({\bf{\{ aba, aa\} }}\)

(c) The result is\({\bf{\{ abb, abab\} }}\)

(d) The result is\({\bf{\{ a}}{{\bf{2}}^{\bf{n}}}{\bf{|n}} \ge {\bf{2\} U\{ }}{{\bf{b}}^{\bf{n}}}{\bf{|n}} \ge {\bf{1\} }}\)

(e) The result is\({\bf{\{ }}{{\bf{a}}^{\bf{n}}}{{\bf{b}}^{{\bf{n + m}}}}{{\bf{a}}^{\bf{m}}}{\bf{|m}} \ge {\bf{0,}}\,{\bf{n}} \ge {\bf{0\} }}\)

Step-by-step solution

about the language generated by the grammar.

Let \({\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)\) be a phrase-structure grammar. The language generated by G (or the language of G), denoted by L(G), and is the set of all strings of terminals that are derivable from the starting state S.

We shall find the language generated by the grammar (V, T, S, P) when the set P of productions consists of\({\bf{S}} \to {\bf{AB}},{\bf{A}} \to {\bf{ab}},{\bf{B}} \to {\bf{bb}}\).

The language is \({\bf{\{ abbb\} }}\)

Explanation:

a. We can derive AB using the start state\({\bf{S}} \to {\bf{AB}}\).

b. Then we can derive \({\bf{abB}}\) using production\(A \to {\bf{ab}}\).

c. Then we can derive \({\bf{abbb}}\) using production\({\bf{B}} \to {\bf{bb}}\).

Hence, we get the result\({\bf{\{ abbb\} }}\).

We shall find the language generated by the grammar (V, T, S, P) when the set P of productions consists of \({\bf{S }} \to {\bf{ AB, S }} \to {\bf{ aA, A }} \to {\bf{ a, B }} \to {\bf{ ba}}{\bf{.}}\)

The language is\({\bf{\{ aba, aa\} }}\).

Explanation:

a. We can derive AB using start state \({\bf{S}} \to {\bf{AB}}\) and \({\bf{aA}}\) using\({\bf{S}} \to {\bf{aA}}\).

b. Then we can derive \({\bf{aB}}\) and aa using production\({\bf{A}} \to {\bf{a}}\).

c. Then we can derive aba and aa using production \({\bf{B}} \to {\bf{ba}}\)

Hence the result {aba, aa}.

We shall find the language generated by the grammar (V, T, S, P) when the set P of productions consists of \({\bf{S }} \to {\bf{ AB, S }} \to {\bf{ AA, A }} \to {\bf{ aB, A }} \to {\bf{ ab, B }} \to {\bf{ b}}{\bf{.}}\)

The language is \({\bf{\{ abb, abab\} }}\)

Explanation:

a. From the start state S, we can derive AB using \({\bf{S}} \to {\bf{AB}}\) and AA using\({\bf{S}} \to {\bf{AA}}\).

b. Then we can derive \({\bf{aBB}}\) and \({\bf{aBaB}}\) using production\({\bf{A}} \to {\bf{aB}}\).

c. Then we can derive abb and \({\bf{abab}}\) using production\({\bf{B}} \to {\bf{b}}\).

Hence, the result is\({\bf{\{ abb, abab\} }}\).

We shall find the language generated by the grammar (V, T, S, P) when the set P of productions consist\({\bf{S }} \to {\bf{ AA, S }} \to {\bf{ B, A }} \to {\bf{ aaA, A }} \to {\bf{ aa, B }} \to {\bf{ bB, B }} \to {\bf{ b}}.\)

We first derive AA using the first rule\({\bf{S}} \to {\bf{AA}}\). The productions for A are \({\bf{A }} \to {\bf{ aaA}}\) and\({\bf{A}} \to {\bf{aa}}\).

Thus, A will consist of strings of the form \({\bf{aa, aaaa, aaaaaa, }}...{\bf{,}}\) strings that contain an even number of a's.

Therefore, the strings of N a's, where N is an even number greater than or equal to 4, will be in the language.

Now, if we derive B using the second rule SB, then the string obtained is one or more b's, as the production rule is \({\bf{B}} \to {\bf{bB}}\) and \({\bf{B}} \to {\bf{b}}\).

Hence, the result is\({\bf{\{ a}}{{\bf{2}}^{\bf{n}}}{\bf{|n}} \ge {\bf{2\} U\{ }}{{\bf{b}}^{\bf{n}}}{\bf{|n}} \ge {\bf{1\} }}\).

We shall find the language generated by the grammar (V, T, S, P) when the set P of productions consist\({\bf{S }} \to {\bf{ AB, A }} \to {\bf{ aAb, B }} \to {\bf{ bBa, A }} \to {\bf{ \lambda , B }} \to {\bf{ \lambda }}.\)

If we apply the rules then the string obtained will consist of some a's, followed by some b's, and finally followed by some a's as\({\bf{S}} \to {\bf{AB}}\),\({\bf{A }} \to {\bf{ aAb}}\) and\({\bf{B }} \to {\bf{ bBa}}\). As \({\bf{A}} \to {\bf{\lambda }}\) and\({\bf{B}} \to {\bf{\lambda }}\), the number of a's and b's can be equal to zero, in the three parts of the string.

Also, the total number of a's and b's will be equal, since\({\bf{S}} \to {\bf{AB}}\),\({\bf{A }} \to {\bf{ aAb}}\) and\({\bf{B }} \to {\bf{ bBa}}\).

Hence the result is\({\bf{\{ }}{{\bf{a}}^{\bf{n}}}{{\bf{b}}^{{\bf{n + m}}}}{{\bf{a}}^{\bf{m}}}{\bf{|m}} \ge {\bf{0,}}\,{\bf{n}} \ge {\bf{0\} }}\).