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

Suggested languages for you:

Americas

Europe

Q30E

Expert-verified
Found in: Page 857

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# a) Construct a phrase-structure grammar for the set of all fractions of the form a/b, where a is a signed integer in decimal notation and b is a positive integer. b) What is the Backus–Naur form for this grammar? c) Construct a derivation tree for +311/17 in this grammar.

a) The productions are, in addition to the productions given above for a signed integer and a positive integer:

S à < signed integer >< slash >< positive integer > < slash > à /.

b) The Backus–Naur form of the grammar G is,

$$\begin{array}{l}S{\bf{ }}:: = < {\rm{ signed integer}}{\bf{ }} > < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\rm{ positive integer}}{\bf{ }} > {\bf{ }}\\ < {\bf{ }}{\rm{slash}}{\bf{ }} > :: = {\bf{ }}/{\bf{ }}\\ < {\bf{ }}{\rm{positive integer}}{\bf{ }} > :: = < {\bf{ }}{\rm{positive digit}}{\bf{ }} > < {\rm{ other digits}} > {\bf{ }}\\ < {\rm{other digits}}{\bf{ }} > :{\bf{ }} = < {\bf{ }}{\rm{integer}}{\bf{ }} > |\lambda {\bf{ }}\\ < {\rm{signed integer}}{\bf{ }} > :: = < {\bf{ }}{\rm{sign}}{\bf{ }} > < {\bf{ }}{\rm{integer}}{\bf{ }} > {\bf{ }}\\ < {\rm{ sign}}{\bf{ }} > :: = - I + {\bf{ }}\\ < {\bf{ }}{\rm{int eger}}{\bf{ }} > :: = < {\bf{ }}{\rm{integer}}{\bf{ }} > < {\bf{ }}{\rm{digit}}{\bf{ }} > l < {\bf{ }}{\rm{digit}}{\bf{ }} > {\bf{ }}\\ < {\rm{digit}}{\bf{ }} > :: = < {\bf{ }}{\rm{positive digit}}{\bf{ }} > |0{\bf{ }}\\ < {\bf{ }}{\rm{positive digit}}{\bf{ }} > :: = 0|1|2|3|4|5|6|7|8|9{\rm{ }}\end{array}$$

c) The derivation tree for +311/17 is,

See the step by step solution

## Step 1: About Backus-Nour form

A type-2 grammar is designated by the notation known as Backus-Naur form.

The left side of a type 2 grammar's production is one non-terminal symbol.

It can merge all of the productions into a single statement using the same left non-terminal symbol à rather than listing each one separately in production,

It use the symbol:: =

Enclose all non-terminal symbols in brackets <>, and it lists all right-hand sides of productions in the same statement, separating them by bars.

## Step 2: The phrase structure grammar expresses fractions of the form a/b, where a is a signed decimal integer and a positive decimal integer.

(a) Start by defining the grammar for a signed integer and a positive integer.

A positive digit is defined as:

$$\begin{array}{c} < {\rm{positive digit}} > \, \to 1\\ < {\rm{positive digit}} > \, \to 2\\ < {\rm{positive digit}} > \, \to 3\\ < {\rm{positive digit}} > \, \to 4\\ < {\rm{positive digit}} > \, \to 5\\ < {\rm{positive digit}} > \, \to 6\\ < {\rm{positive digit}} > \, \to 7\\ < {\rm{positive digit}} > \, \to 8\\ < {\rm{positive digit}} > \, \to 9\end{array}$$

Adding a production for the digit 0 will give the productions for a digit:

<digit > $$\to$$ < positive digit >

<digit > $$\to$$ 0

An integer is a sequence of digits, so the productions for an integer will be:

< integer > $$\to$$ < integer >< digit >

< integer > $$\to$$ < digit >

A signed integer can be produced from an integer with the following productions:

<signed integer> $$\to$$ <sign><integer>

<sign> $$\to$$ -

<sign> $$\to$$ +

While for a positive integer, the productions just require adding a few productions to the productions for an integer, that is:

<positive integer> $$\to$$ < positive digit >< other digits >

<other digits> $$\to$$ < integer >

<other digits > $$\to$$ $$\lambda$$

Using the productions for an integer and a positive integer, the phrase structure grammar $$G{\bf{ }} = {\bf{ }}\left( {V,{\bf{ }}T,{\bf{ }}S,{\bf{ }}P} \right)$$ for a / b will be:

$$V{\bf{ }} = {\bf{ }}\left\{ {0,1,2,3,4,5,6,7,8,9,{\bf{ }} + ,{\bf{ }} - ,{\bf{ }}/,{\bf{ }}{\rm{sign, digit, positive digit, integer, signed integer, positive integer, slash}},{\bf{ }}S} \right\}$$

$$T = {\bf{ }}\left\{ {0,1,2,3,4,5,6,7,8,9,{\bf{ }} + ,{\bf{ }} - } \right\}$$

Hence, the productions are, in addition to the productions given above for a signed integer and a positive integer:

S $$\to$$ < signed integer >< slash >< positive integer > < slash > $$\to$$ /.

## Step 3: Backus-Naur form of productions of the above grammar.

(b) The productions for the grammar created for part (a), all have a single non-terminal on the left-hand side.

Thus, this grammar is type 2 grammar.

The grammar is converted to the Backus-Naur form by combining the productions which have the same non-terminal on the left-hand side into a single product; and by replacing " with:: =”

This gives the following productions.

$$\begin{array}{l}S{\bf{ }}:: = < {\bf{ }}{\rm{signed integer}}{\bf{ }} > < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positive integer}}{\bf{ }} > {\bf{ }}\\ < {\bf{ }}{\rm{slash}}{\bf{ }} > :: = {\bf{ }}/{\bf{ }}\\ < {\bf{ }}{\rm{positive integer}}{\bf{ }} > :: = < {\bf{ }}{\rm{positive digit}}{\bf{ }} > < {\bf{ }}{\rm{other digits}} > {\bf{ }}\\ < {\rm{other digits}}{\bf{ }} > :{\bf{ }} = < {\bf{ }}{\rm{integer}}{\bf{ }} > |\lambda {\bf{ }}\\ < {\rm{signed integer}}{\bf{ }} > :: = < {\bf{ }}{\rm{sign}}{\bf{ }} > < {\rm{ integer}}{\bf{ }} > {\bf{ }}\\ < {\bf{ }}{\rm{sign}}{\bf{ }} > :: = - I + {\bf{ }}\\ < {\bf{ }}{\rm{int eger}}{\bf{ }} > :: = < {\bf{ }}{\rm{integer}}{\bf{ }} > < {\bf{ }}{\rm{digit}}{\bf{ }} > l < {\bf{ }}{\rm{digit}}{\bf{ }} > {\bf{ }}\\ < {\rm{digit}}{\bf{ }} > :: = < {\bf{ }}{\rm{positive digit}}{\bf{ }} > |0{\bf{ }}\\ < {\rm{ positive digit}}{\bf{ }} > :: = 0|1|2|3|4|5|6|7|8|9{\rm{ }}\end{array}$$

Hence, the above productions is The Backus–Naur of productions form of the grammar G.

## Step 4: To get the derivation tree for +311/7 first we do a top-down derivation for it, which is:

(c) Now, the deviation is

$$\begin{array}{c}S{\bf{ }} = > < {\bf{ }}{\rm{signed integer}}{\bf{ }} > < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positive integer}}{\bf{ }} > {\bf{ }}\\ = > < {\bf{ }}{\rm{sign}}{\bf{ }} > < {\bf{ }}{\rm{integer}}{\bf{ }} > < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positive integer}}{\bf{ }} > {\bf{ }}\\ = > {\bf{ }} + {\bf{ }} < {\rm{integer}}{\bf{ }} > < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positive}}\,\,{\rm{integer}} > {\bf{ }}\\ = > {\bf{ }} + {\bf{ }} < {\bf{ }}{\rm{integer}}{\bf{ }} > < {\bf{ }}{\rm{digit}}{\bf{ }} > < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positive integer}}{\bf{ }} > \\ = > {\bf{ }} + {\bf{ }} < {\rm{integer}}{\bf{ }} > {\bf{ }}|{\bf{ }} < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positiveinteger}} > {\bf{ }}\\ = > {\bf{ }} + {\bf{ }} < {\bf{ }}{\rm{integer}}{\bf{ }} > < {\bf{ }}{\rm{digit}}{\bf{ }} > {\bf{ }}||{\bf{ }} < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positive integer}}{\bf{ }} > {\bf{ }}\\ = > {\bf{ }} + {\bf{ }} < {\bf{ }}{\rm{integer}}{\bf{ }} > {\bf{ }}||{\bf{ }} < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positive}}\,\,{\rm{integer}} > {\bf{ }}\\ = > {\bf{ }} + {\bf{ }} < {\bf{ }}{\rm{digit}}{\bf{ }} > {\bf{ }}||{\bf{ }} < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positive}}\,\,{\rm{integer}}{\bf{ }} > \\ = > {\bf{ }} + 311{\bf{ }} < {\bf{ }}{\rm{slash}}{\bf{ }} > < {\bf{ }}{\rm{positive integer}}{\bf{ }} > {\bf{ }}\\ = > {\bf{ }} + 311/{\bf{ }} < {\bf{ }}{\rm{positive}}\,\,{\rm{integer}} > {\bf{ }}\\ = > {\bf{ }} + 311/{\bf{ }} < {\bf{ }}{\rm{positive digit}}{\bf{ }} > < {\bf{ }}{\rm{other digits}}{\bf{ }} > {\bf{ }}\\ = > {\bf{ }} + 311/{\bf{ }}7{\bf{ }} < {\bf{ }}{\rm{other digits}}{\bf{ }} > \\ = > {\bf{ }} + 311/{\bf{ }}7\lambda {\bf{ }}\\ = > + 311/7{\bf{ }}\end{array}$$

Let’s construct a derivation tree for +311/17 in the above grammar is.

Hence, the above derivation tree for +311/17.