Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Short Answer

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.

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

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

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.

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

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}\)

Step by Step Solution

Step 1: Definition of top-down parsing

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

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

Step 4: Using top-down parsing to determine ‘\({\bf{abab}}\)’ string 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.

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

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

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}\)

Step by Step Solution

Step 1: Definition of top-down parsing

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

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

Step 4: Using top-down parsing to determine ‘\({\bf{abab}}\)’ string 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.

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

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths

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}\)