• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q25E

Expert-verified Found in: Page 857 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # use top-down parsing to determine whether each of the following strings belongs to the language generated by the grammar in Example 12.$$\begin{array}{*{20}{l}}{{\bf{a) baba}}}\\{{\bf{b) abab}}}\\{{\bf{c) cbaba}}}\\{{\bf{d) bbbcba}}}\end{array}$$

(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.

See the step by step solution

## Step 1: Definition of top-down parsing

To find out rather a word belongs to the language made by a phrase structure grammar, the way to approach the problem is to start with S, the beginning symbol and anything empty to decide the required word using a series of productions is called top-down parsing.

## Step 2: Writing the language generated by the grammar from Example 12.

The language made 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 symbol 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}$$

## Step 3: Using top-down parsing to determine ‘$${\bf{baba}}$$’ string belongs to the language generated by G.

(a)

Using the given information and let’s starting the symbol ‘S’;

$$\begin{array}{c}S \to AB{\bf{ }}\\ \to {\bf{ }}CaB{\bf{ }}\\ \to {\bf{ }}baB{\bf{ }}\\ \to {\bf{ }}baBa{\bf{ }}\\ \to {\bf{ }}baba{\bf{ }}\end{array}$$

Hence, ‘$${\bf{baba}}$$’ belong to the language generated by G.

## Step 4: Using top-down parsing to determine ‘$${\bf{abab}}$$’ string belong to the language generated by G.

(b)

Since $$S \to AB,{\bf{ }}A \to {\bf{ }}Ca,{\bf{ }}C \to {\bf{ }}cb,{\bf{ }}C \to {\bf{ }}b$$ are the only options, any sentence starts with either c or b.

Hence ‘$${\bf{abab}}$$’ does not belong to the language generated by G.

## Step 5: Use top-down parsing to determine ‘$${\bf{cbaba}}$$’ string belongs to the language generated by G.

(c)

Using the given information and let’s start the symbol ‘S’;

$$\begin{array}{c}S \to AB{\bf{ }}\\ \to {\bf{ }}caB{\bf{ }}\\ \to {\bf{ }}cbaB{\bf{ }}\\ \to {\bf{ }}cbaBa{\bf{ }}\\ \to {\bf{ }}cbaba{\bf{ }}\end{array}$$

Hence, ‘$${\bf{cbaba}}$$’ belong to the language generated by G.

## Step 6: Using top-down parsing to determine ‘$${\bf{bbbcba}}$$’ string belongs to the language generated by G.

(d)

Since $$S \to AB,{\bf{ }}A \to {\bf{ }}Ca,{\bf{ }}C \to {\bf{ }}cb,{\bf{ }}C \to {\bf{ }}b.$$are the only options, any sentence starts with either cba or ba.

Hence ‘$${\bf{bbbcba}}$$’ does not belong to the language generated by G. ### Want to see more solutions like these? 