I’m trying to understand what a regular language is. There are 3 compound regular expressions for regular language: concat {AB}, union {A+B} and iteration {A*}. When they are used in a simple ways it’s clear for me how operate with them. But I’m frustrated with questions like this:
Find regular language equivalent to: (0 + 1)*1(0 + 1)*
(01 + 11)*(0 + 1)*
(0 + 1)*(10 + 11 + 1)(0 + 1)*
(1 + 0)*1(1 + 0)*
(0 + 1)*(0 + 1)(0 + 1)*
As I understand that instead of (0 + 1)* it can be "", so equivalent language should have at least 1 and any number of symbols before and after it.
(01 + 11)*(0 + 1)* can evaluate to "", wrong
(0 + 1)*(10 + 11 + 1)(0 + 1)* can evaluate to 10 or 11 or 1, can be solution
(1 + 0)*1(1 + 0)* has middle one, can be a solution
(0 + 1)*(0 + 1)(0 + 1)* has (0+1) and can be or 0 or 1 or "", wrong
Are my guesses correct?
3
The given language amounts to “any bit string with at least one 1 in it”, so your guesses are correct. Option 4 is equivalent because union is symmetrical, so (0 + 1) is equivalent to (1 + 0). Option 2 is equivalent because however you expand the iterations in option 2, you can just expand the iterations in the given regex once more to make up the difference, and conversely, if you expand both iterations in the given regex to “”, then you get just 1, which is explicitly allowed by option 2 as well.
In general, proving equivalence amounts to (1) proving that any string generated by A can be generated by B and vice versa or (2) transforming both expressions until they are identical. Noticing that (1 + 0) is equivalent to (0 + 1) is an instance of method (2), arguing like “you can always choose one iteration more” is an instance of method (1).