We want to define the set S of strings with the same number of a's and b's using induction. Example strings in S ab, ba, aabb, abab, abba, baab, baba, bbaa, aaabbb, aababb, abbbab,......How do we know if a string is in S? We usually rely on counting the number of a's and b's, and do a comparison of the two counts. But we can de ne the set S inductively without resorting to counting. Base case: the empty string lamda is in S. Inductive Step: Case 1: If string s is in S, then we include the string a s b in S. Case 2: If string s is in S, then we include the string b s a in S. Case 3: If strings s and t are in S, then we include the string s t in S. Finally, we say that strings that are not generated by the base case or the inductive step are not in S.

Q. Show by induction in plain English that strings in S have the same number of a's and b's. and also Show that any string that has the same number of a's and b's is included in S.