1

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
  • Regular expressions usually use | to express union. What does + mean in your formalism? Commented Nov 12, 2014 at 21:34
  • @KilianFoth + means union) Commented Nov 13, 2014 at 6:12
  • + can be used in Mathematics to denote the disjoint union of two sets.
    – Giorgio
    Commented Nov 13, 2014 at 6:45

1 Answer 1

2

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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.