Question

use bottom-up parsing to determine whether the strings in Exercise 25 belong to the language generated by the grammar in Example 12.

Short answer

(a) Yes, \(baba\) belong to the language generated by G.

(b) No, \(abab\) does not belong to the language generated by G.

(c) Yes, \(cbaba\) belong to the language generated by G.

(d) No, \(bbbcba\) does not belong to the language generated by G.

Step-by-step solution

Definition of Bottom-up parsing

Bottom-up parsing uses production steps starting from the given string to derive S. If S is not obtained, then the string cannot be generated by the grammar.

Writing the language generated by the grammar from Example 12 and the strings from Exercise 25.

The language produced by the grammar \(G{\bf{ }} = {\bf{ }}\left( {V,{\bf{ }}T,{\bf{ }}S,{\bf{ }}P} \right)\), where \(V{\bf{ }} = {\bf{ }}\left\{ {a,{\bf{ }}b,{\bf{ }}c,{\bf{ }}A,{\bf{ }}B,{\bf{ }}C,{\bf{ }}S} \right\}\), \(T{\bf{ }} = {\bf{ }}\left\{ {a,{\bf{ }}b,{\bf{ }}c} \right\}\), S is the sign of beginning, and the productions are

\(\begin{array}{c}S \to AB{\bf{ }}\\A \to {\bf{ }}Ca{\bf{ }}\\B \to {\bf{ }}Ba{\bf{ }}\\B \to {\bf{ }}Cb{\bf{ }}\\B \to {\bf{ }}b{\bf{ }}\\C \to {\bf{ }}cb{\bf{ }}\\C \to {\bf{ }}b.\end{array}\)

The strings from exercise 25.

\(\begin{array}{*{20}{l}}{a){\bf{ }}baba}\\{b){\bf{ }}abab}\\{c){\bf{ }}cbaba}\\{d){\bf{ }}bbbcba}\end{array}\)

Using Bottom-up parsing to determine ‘\({\bf{baba}}\)’ string belong to the language generated by G.

(a)

The string is \(baba\),

Use the production C \(\to\) b, so baba \(\to\) Caba.

Then use the production A \(\to\) Ca, so that Caba \(\to\) Aba.

Using the production B \(\to\) b gives Aba \(\to\) ABa.

Then use the production B \(\to\) Ba, so that ABa \(\to\) AB.

Finally, using A \(\to\) AB shows that the complete derivation for \(baba\) is

\(\begin{array}{c}S \to AB{\bf{ }}\\ \to {\bf{ }}ABa{\bf{ }}\\ \to {\bf{ }}Aba{\bf{ }}\\ \to {\bf{ }}Cabb{\bf{ }}\\ \to {\bf{ }}baba{\bf{ }}\end{array}\)

Thus, ‘baba’ belongs to the language generated by the grammar.

Using Bottom-up parsing to determine ‘\({\bf{abab}}\)’ string belong to the language generated by G.

(b)

The string is ‘\(abab\)’.

From the production steps, observe that a is on the right side, this implies that a string cannot start with a.

Thus, the string does not belong to the language generated by the grammar.

Using Bottom-up parsing to determine ‘\({\bf{cbaba}}\)’ string belongs to the language generated by G.

(c)

The string is ‘\(cbaba\)’.

Use the production C \(\to\) cb, so cbaba \(\to\) Caba.

Then use the production A \(\to\) Ca, so that Caba \(\to\) Aba.

Using the production B \(\to\) b gives Aba \(\to\) ABa.

Then use the production B \(\to\) Ba, so that ABa \(\to\) AB.

Finally, using S \(\to\) AB shows that the complete derivation for ‘baba’ is

\(\begin{array}{c}S \to AB{\bf{ }}\\ \to {\bf{ }}ABa{\bf{ }}\\ \to {\bf{ }}Aba{\bf{ }}\\ \to {\bf{ }}Caba{\bf{ }}\\ \to {\bf{ }}cbaba{\bf{ }}\end{array}\)

Hence, ‘cbaba’ belongs to the language generated by the grammar.

Using Bottom-up parsing to determine ‘\({\bf{bbbcba}}\)’ string belong to the language generated by G.

(d)

The string is ‘\(bbbcba\)’.

Now Use the production C \(\to\) cb, so bbbcba \(\to\) bbbCa

Then use the production A \(\to\) Ca, so that bbbCa \(\to\) bbbA.

From the production steps, observe that none of the steps has a right side starting with A, this implies that a string cannot end with A.

Thus, the string does not belong to the language generated by the grammar.