Question

Describe the set of strings defined by each of these sets of productions in EBNF.

\(\begin{array}{c}\left( {\bf{a}} \right){\bf{string :: = L + D?L + }}\\{\bf{L :: = a }}\left| {{\bf{ b }}} \right|{\bf{ c }}\\{\bf{D :: = 0 | 1}}\\\left( {\bf{b}} \right){\bf{string :: = signD + |D + }}\\{\bf{sign :: = + | - }}\\{\bf{D :: = 0 | 1|2|3|4|5|6|7|8|9}}\\\left( {\bf{c}} \right){\bf{string :: = L*}}\left( {{\bf{D + }}} \right){\bf{?L* }}\\{\bf{L :: = x |y }}\\{\bf{D :: = 0 | 1}}\end{array}\)

Short answer

Answer

a. The letters used are a, b and c and the binary digits are 0 and 1.

b. The sign is + or - and digits are 0 to 9.

c. The letters are x and y and the digits are 0 and 1.

Step-by-step solution

About Backus-Nour form

The Backus-Naur form is a notation for specifying a type 2 grammar.

A type-2 grammar has a single non-terminal symbol on the left side of each production.

Instead of listing all productions individually, we can combine all productions with the same non-terminal symbol on the left into one statement instead of using the symbolàin a production,

The symbol:: =

List all right-hand sides of productions in the same statement, with bars separating them, and enclose any non-terminal symbols in brackets (>).

The Backus-Naur form's additions include the following:

"+": denotes that the symbol to the left of it may appear once or more.

The symbol or group of symbols in the parenthesis to its left may appear as 0 or 1, according to the symbol "?"

"*": denotes that the sign to the left of it may appear once or more.

a. In this, a string is formed of one or more letters, followed by an optional binarydigit and ending with one or more letters.

Here the letters used are a, b and c and the binary digits are 0 and 1.

b. The string consists of an optional sign, followed by one or more digits.

Here the sign is + or - and digits are 0 to 9.

c. The string consists of any number of letters, optionally followed by one or more number of digits and ending with any number of letters.

Here the letters are x and y and the digits are 0 and 1.