Tutorial 7

Just skimmed through the handout of tutorial 7. My thoughts so far:

1. Prove or disprove that if RS == SR => R == S (let this statement be our predicate)
Let S and R be two regular expressions
To disprove, we only need to find a counter example.
Let R = (0 + 1)*
and S = 1*
So, RS = (0 + 1)*1* and SR = 1*(0 + 1)*
Note that the string "01" is accepted by both RS and SR, so RS == SR
But, R != S, so this is a contradiction!
Therefore we've disproved the statement

2. Devise a regex R for all strings of {0, 1}* that start and end with the same bit (e.g. 1001101, 01000, etc.)
R1 = 1(0 + 1)*1 -> a string that starts with 1, followed by 0 or more occurences of {0, 1}, ends with 1
R2 = 0(0 + 1)*0 -> a string that starts with 0, followed by 0 or more occurences of {0, 1}, ends with 0
R = R1 + R2 = (0(0 + 1)*0) + (1(0 + 1)*1) -> R1 or R2

Proof of correctness:
I still don't know how to write a formal proof for this regex. I'll update this post sometime after the tutorial tomorrow.