A set T of strings is defined recursively by 1 pqq belong to

A set T of strings is defined recursively by

1. pqq belong to T.
2. If x and y belong to T, so do pxqq, qqxp, and xy.

Use structural induction to prove that every string in T has twice as many q\'s as p\'s.

Solution

“The string contains an even number of q’s”

The property is true for the objects in BASE, since the base consists of only object e: ,
which contains 0 q’s, and because 0 is an even number and e contains an even number of

q’s.

For each rule in the RECURSION for T, if the rule is applied to an object in T that
Satises the property, then the objects dened by the rule also satisfy the property

The recursion for S consists of four rules dened as pxqq, qqxp, andxy.

Supposes is a string in T that contains an even number of q’s.
In the case Where either pxqq or qqxp is applied to s, the result is the strinng; or the
string yx. Each of these contains the same number of q’s as T, and thus an even number of

q’s.

In the case where either rule xy is applied to s, the result is the string pxqq, qqxp each of
these contain two more q’s than the number of q’s in T. Because two more than any even
number is an even integer, both pxqq, qqxgv contain an even number of q \'s.

Thus, when each rule in the RECURSION is applied to a string in T that contains an even
number of q’s, the result is also a string that contains an even number of q’s.

Thus, the property is true.