[Math] Regular Expression Notation

regular expressions

I'm doing a theory of computation course and can't for the life of me find any good resource that will tell me how a regular expression such as (a+b)* converts to set form. I've thought of a binary one that I might be able to answer if I find this information:

(1+ (01)*)10

Would this simply be a string that starts with 1 and ends with 10 with all strings over {0, 1} in the middle of the string?

Best Answer

In regex, + means 'one or more', while * means 'zero or more'.

So in words your expression is: one or more 1s, followed by zero or more 01s, followed by 10.

For example, 1111101010110 or 110 are both valid, but 01010110 and 111010 are not.

That doesn't actually line up with your earlier example of (a+b)* though, where the * acts on an expression with a + in it. That means zero or more of (one or more as, followed by b).

So take any expressions with several a's followed by a b: aaab, ab, aab, and put them together: aaababaab is valid. So is the empty string, since the star allows 0 such expressions. (In this specific case, a more simpler wording is: every b much be preceded by at least one a).

Related Question