Logout Open In App
Open In App
Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Chapter 13: Q23E (page 857)

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

Expert verified

(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

01

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

02

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.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Express each of these sets using a regular expression.

  1. The set consisting of the strings 0, 11, and 010
  2. The set of strings of three 0s followed by two or more 0s
  3. The set of strings of odd length
  4. The set of strings that contain exactly one 1
  5. The set of strings ending in 1 and not containing 000

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.

Show that if \({\bf{M = (S,I,f,}}{{\bf{s}}_{\bf{o}}}{\bf{,F)}}\) is a deterministic finite state automaton and f (s, x)=sfor the state s∈Sand the input string x∈I*, then \({\bf{f(s,}}{{\bf{x}}^{\bf{n}}}{\bf{)}}\)=sfor every nonnegative integer n. (Here \({{\bf{x}}_{\bf{n}}}\) is the concatenation of ncopies of the string x, defined recursively in Exercise 37in Section 5.3.)

a) Explain what the productions are in a grammar if the Backus–Naur form for productions is as follows:

\(\begin{array}{*{20}{l}}{{\bf{ < expression > :: = }}\left( {{\bf{ < expression > }}} \right){\bf{ }}\left| {{\bf{ < expression > + < expression > }}} \right|}\\\begin{array}{c}{\bf{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;}}\,\,\,\,{\bf{ < expression > * < expression > |}}\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{\bf{ < variable > }}\end{array}\\{\,\,\,\,\,\,\,\,\,{\bf{ < variable > :: = xly}}}\end{array}\)

b) Find a derivation tree for \(\left( {{\bf{x*y}}} \right){\bf{ + x}}\) in this grammar.

Given a deterministic finite-state automaton \({\bf{M = (S,I,f,}}{{\bf{s}}_{\bf{o}}}{\bf{,F)}}\), use structural induction and the recursive definition of the extended transition function f to prove that \({\bf{f }}\left( {{\bf{s, x y}}} \right){\bf{ = f }}\left( {{\bf{f }}\left( {{\bf{s ,x}}} \right){\bf{, y}}} \right)\)for all states \({\bf{s}} \in {\bf{S}}\)and all strings\({\bf{x}} \in {\bf{I}}*{\bf{andy}} \in {\bf{I}}*\).
See all solutions

Recommended explanations on Math Textbooks

Logic and Functions

Read Explanation

Applied Mathematics

Read Explanation

Statistics

Read Explanation

Theoretical and Mathematical Physics

Read Explanation

Pure Maths

Read Explanation

Geometry

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free