Question

Give two examples of how well-formed formulae are defined recursively for different sets of elements and operators.

Short answer

1) Thus,\({\rm{sm1}} \in {\rm{S whenever s}} \in {\rm{S and m}} \in {\rm{S}}\).

2) Thus,\(1s1 \in S{\rm{ whenever s}} \in {\rm{S}}{\rm{.}}\)

Step-by-step solution

Well–formed the formula.

We can recursively define a set of well-formed formulas consisting of variables, numerals, and operators from the set\(\left\{ { + , - ,*,/, \uparrow } \right\}\)recursive.

Palindromes.

A 4-digit number is called a palindrome if it is the same when the digits are read in reverse.

Step 3:1) Example.

Set \(S\) of bit strings that have more zero than ones.

\(\begin{array}{c}0 \in S\\sm \in S{\rm{ whenever s}} \in {\rm{S and m}} \in {\rm{S}}{\rm{.}}\\{\rm{1sm}} \in {\rm{S whenever s}} \in {\rm{S and m}} \in {\rm{S}}{\rm{.}}\\{\rm{s1m}} \in {\rm{S whenever s}} \in {\rm{S and m}} \in {\rm{S}}{\rm{.}}\\{\rm{sm1}} \in {\rm{S whenever s}} \in {\rm{S and m}} \in {\rm{S}}{\rm{.}}\end{array}\)

Step 4:2)Example.

Set \(S\) of bit strings that are palindromes.

\(\begin{array}{c}\lambda \in S\\0 \in S\\1 \in S\\0s0 \in S{\rm{ whenever s}} \in {\rm{S}}{\rm{.}}\\1s1 \in S{\rm{ whenever s}} \in {\rm{S}}{\rm{.}}\end{array}\)