A set of T strings is defined recursively by 1 pqq belongs t

A set of T strings is defined recursively by
1. pqq belongs 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.
*Please don\'t copy and paste the answer that has already been posted to chegg...this is my second time posting this question

Solution

A set of T strings is defined recursively by
1. pqq belongs to T.
2. if x and y belong to T, so do pxqq, qqxp, and xy.

Base case: If empty string belongs to T

so {pqq, qqp} belongs to T

Lets consider it is true for string of length k.

To prove that it is true for string of length k+1

Let X_k+1 be a string of k+1 length, we have to prove {pX_k+1qq, qqX_k+1p} belongs to T

let X_k be a string of length k so {pX_kqq, qqX_kp} belongs to T.

X_k+1 can be written as X_kY so {pX_kYqq, qqX_kYp} belongs to T

so it is proved that every string in T has twice as many q\'s as p\'s.