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 11: Q32E (page 784)

Give a definition of well-formed formulae in postfix notation over a set of symbols and a set of binary operators.

Short Answer

Expert verified

A well-formed formula in postfix notation over a set of symbols and a set of binary operators are defined recursively by these rules:

  1. If x is a symbol, then x is a well-formed formula in postfix notation;
  2. If X and Y are well-formed formulae and \( * \) is an operator, then \( * {\bf{YX}}\) is a well-formed formula.

Step by step solution

Achieve better grades quicker with Premium

  • Unlimited AI interaction
  • Study offline
  • Say goodbye to ads
  • Export flashcards
Start your free trial Skip

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

01

General form

Well-formed formulaein prefix notation over a set of symbols and a set of binary operators are defined recursively by these rules:

  1. If x is a symbol, then x is a well-formed formula in prefix notation;
  2. If X and Y are well-formed formulae and \( * \) is an operator, then \( * {\bf{XY}}\) is a well-formed formula.
02

Definition for well-formed formulae

The only difference between a formula in postfix notation and prefix notation is that the order of the elements in reversed.

This implies that we only require to make 2 adjustments to the definition of a well-formed formulae in prefix notation:

Point 1: Replace “prefix” with “postfix”

Point 2: Replace \( * {\bf{XY}}\) by \( * {\bf{YX}}\). Since the order of the element is reversed.

Now, the definition is shown below:

Well-formed formulaein postfix notation over a set of symbols and a set of binary operators are defined recursively by these rules:

  1. If x is a symbol, then x is a well-formed formula in postfix notation;
  2. If X and Y are well-formed formulae and \( * \) is an operator, then \( * {\bf{YX}}\) is a well-formed formula.

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

Show that Sollin’s algorithm requires at most \({\bf{logn}}\) iterations to produce a minimum spanning tree from a connected undirected weighted graph with \({\bf{n}}\) vertices.

Sollin's algorithm produces a minimum spanning tree from a connected weighted simple graph \({\bf{G = (V,E)}}\) by successively adding groups of edges. Suppose that the vertices in \({\bf{V}}\) are ordered. This produces an ordering of the edges where \({\bf{\{ }}{{\bf{u}}_{\bf{0}}}{\bf{,}}{{\bf{v}}_{\bf{0}}}{\bf{\} }}\) precedes \({\bf{\{ }}{{\bf{u}}_{\bf{1}}}{\bf{,}}{{\bf{v}}_{\bf{1}}}{\bf{\} }}\) if \({{\bf{u}}_{\bf{0}}}\) precedes \({{\bf{u}}_{\bf{1}}}\) or if \({{\bf{u}}_{\bf{0}}}{\bf{ = }}{{\bf{u}}_{\bf{1}}}\) and \({{\bf{v}}_{\bf{0}}}\) precedes \({{\bf{v}}_{\bf{1}}}\). The algorithm begins by simultaneously choosing the edge of least weight incident to each vertex. The first edge in the ordering is taken in the case of ties. This produces a graph with no simple circuits, that is, a forest of trees (Exercise \({\bf{24}}\) asks for a proof of this fact). Next, simultaneously choose for each tree in the forest the shortest edge between a vertex in this tree and a vertex in a different tree. Again the first edge in the ordering is chosen in the case of ties. (This produces a graph with no simple circuits containing fewer trees than were present before this step; see Exercise \({\bf{24}}\).) Continue the process of simultaneously adding edges connecting trees until \({\bf{n - 1}}\) edges have been chosen. At this stage a minimum spanning tree has been constructed.

Show that the addition of edges at each stage of Sollin’s algorithm produces a forest.

Build a binary search tree for the word’s banana, peach, apple, pear, coconut, mango, and papaya using alphabetical order.

a. What is a minimum spanning tree of a connected weighted graph\(?\)

b. Describe at least two different applications that require that a minimum spanning tree of a connected weighted graph be found.

Show that the first step of Sollin’s algorithm produces a forest containing at least \(\left\lceil {\frac{n}{2}} \right\rceil \) edges when the input isan undirected graph with \(n\) vertices.
See all solutions

Recommended explanations on Math Textbooks

Theoretical and Mathematical Physics

Read Explanation

Calculus

Read Explanation

Probability and Statistics

Read Explanation

Decision Maths

Read Explanation

Statistics

Read Explanation

Mechanics Maths

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