2

My question is pretty straightforward: Give a recursive definition for the set of all strings of a’s and b’s, where all the strings are of even length.

I have attempted to solve the above question and I was wondering if you could tell me if my solution is correct or on the right track.

Updated solution

Base: ∈ S

Recursion: if s ∈ S

aas ∈ S

abs ∈ S

bas ∈ S

bbs ∈ S

bcsoccer5
  • 21
  • Base case: $\epsilon \in S$. – lhf Aug 08 '22 at 21:48
  • Sorry but could you help me understand how I would solve this if ∈ ? In that case, would it be s "if s∈, s∈ s∈" Is that not too broad since I have to shown a and b would be an element first? – bcsoccer5 Aug 08 '22 at 22:02
  • 1
    No, @lhf is saying that your base case should be that $\varepsilon$ (the empty string) is in $S$ (since it has even length, $0$, and vacuously contains only $a$'s and $b$'s). The recursive step is already correct. Unlike with your current base case, you can now show that $ba$, $aa$, and $bb$ (and strings starting with those pairs) belong to $S$. – mjqxxxx Aug 08 '22 at 22:18
  • Thank you both, it makes sense now. I've updated by recursion step as well! – bcsoccer5 Aug 08 '22 at 23:00
  • Not sure your recursion step is correct anymore... now it only generates strings with equal numbers of $a$'s and $b$'s. (For instance, now $bb\not\in S$.) – mjqxxxx Aug 08 '22 at 23:17
  • Sorry, when I said I updated it, I meant on my actual assignment. I updated here as well if you would like to double check! – bcsoccer5 Aug 09 '22 at 02:24

0 Answers0