Question

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

Short answer

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

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.

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.