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?

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

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