• :00Days
  • :00Hours
  • :00Mins
  • 00Seconds
A new era for learning is coming soonSign up for free
Log In Start studying!

Select your language

Suggested languages for you:
Deutsch (DE)
Deutsch (UK)
Deutsch (US)

Americas

Europe

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

Q2E

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

Discrete Mathematics and its Applications

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.

Register for Free I’ll do it later
Illustration

Short Answer

Find five other valid sentences, besides those given in Exercise 1.

(a) The sleepy hare runs quickly

(b) The happy hare runs slowly.

(c) The happy tortoise passes the hare

(d) The hare passes the tortoise.

(e) The tortoise passes the happy hare

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :
TABLE OF CONTENTS

Step 1: Describe the sentences of a formal language using grammar.

The use of grammar helps when we consider the two classes of problems that arise most frequently in applications to programming languages:

(1) How can we determine whether a combination of words is a valid sentence in a formal language?

(2) How can we generate valid sentences in a formal language? Before giving a technical definition of grammar,

Step 2: Firstly, Use the given notation

Given notation is:

\({\bf{Sentence}} \to {\bf{noun phrase transitive verb phrase noun phrase}}\)

\({\bf{Sentence}} \to {\bf{noun phrase intransitive verb phrase}}\)

\({\bf{Noun phrase}} \to {\bf{article adjective noun}}\)

\({\bf{Noun phrase}} \to {\bf{article noun}}\)

\({\bf{Transitive verb phrase}} \to {\bf{transitive verb\;}}\)

\({\bf{Intransitive verb phrase}} \to {\bf{intransitive verb adverb}}\)

\({\bf{Intransitive verb phrase}} \to {\bf{in transitive verb}}\)

\({\bf{Article}} \to {\bf{the}}\)

\({\bf{Adjective}} \to {\bf{sleepy}}\)

\({\bf{Adjective}} \to {\bf{happy}}\)

\({\bf{Noun}} \to {\bf{tortoise}}\)

\({\bf{Noun}} \to {\bf{hare}}\)

\({\bf{Transitive verb}} \to {\bf{passes}}\)

\({\bf{Intransitive verb}} \to {\bf{runs}}\)

\({\bf{Adverb}} \to {\bf{quickly}}\)

\({\bf{Adverb}} \to {\bf{slowly}}\)

Step 3: Now find the first valid sentence.

Noun phrase intransitive verb phrase:

(Article, adjective, noun) intransitive verb phrase

(Article, adjective, noun, intransitive verb phrase, adverb)

Hence, the sentence is: the sleepy hare runs quickly.

Step 4: Now find the second valid sentence.

Noun phrase intransitive verb phrase:

(Article, adjective, noun) intransitive verb phrase

(Article, adjective, noun, intransitive verb phrase, adverb)

Hence, the sentence is: the happy hare runs slowly.

Step 5: Now find the third valid sentence.

Noun phrase transitive verb phrase:

(Article, adjective, noun) transitive verb phrase

(Article, adjective, noun, transitive verb phrase, noun phrase)

(Article, adjective, noun, transitive verb phrase, article, noun)

Hence, the sentence is: the happy tortoise passes the hare.

Step 6: Now find the fourth valid sentence.

Noun phrase transitive verb phrase:

(Article, noun) transitive verb phrase

(Article, noun, transitive verb phrase, noun phrase)

(Article, noun, transitive verb phrase, article, noun)

Hence, the sentence is: the hare passes the tortoise.

Step 7: Now find the fifth valid sentence.

Noun phrase transitive verb phrase:

(Article, noun) transitive verb phrase

(Article, noun, transitive verb phrase, noun phrase)

(Article, noun, transitive verb phrase, article, adjective, noun)

Hence, the sentence is: The tortoise passes the happy hare.

Most popular questions for Math Textbooks

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

Show that a set is generated by a regular grammar if and only if it is a regular set.

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.

Determine whether each of these strings is recognized by the deterministic finite-state automaton in Figure 1.

a) 010b) 1101 c) 1111110d) 010101010

Let G be a grammar and let R be the relation containing the ordered pair \(\left( {{{\bf{w}}_{\bf{0}}}{\bf{,}}\,{{\bf{w}}_{\bf{1}}}} \right)\) if and only if \({{\bf{w}}_{\bf{1}}}\) is directly derivable from \({{\bf{w}}_{\bf{0}}}\) in G. What is the reflexive transitive closure of R?
Icon

Want to see more solutions like these?

Sign up for free to discover our expert answers
Get Started - It’s free

Recommended explanations on Math Textbooks

Decision Maths

Read explanation

Calculus

Read explanation

Probability and Statistics

Read explanation

Statistics

Read explanation

Mechanics Maths

Read explanation

Geometry

Read explanation

Pure Maths

Read explanation

94% of StudySmarter users get better grades.

Sign up for free
94% of StudySmarter users get better grades.