Question about Regular Expressions, DFA and relations

Question

I have a few questions about discrete math, I can't fully grasp these concepts. For regular expression, what does the U symbol mean, at first I thought it meant that it was similar to or, for example (10 U 010 U 01)* would mean any number of combinations between 10 010 01, and you can using any amount of those 3 numbers, for example 10010011001 would be in that language. Another example would be that '01' and '10' are contained within a string: 0 (01 U 10 )^* 1 But I'm not exactly sure. Also, how would I go about converting (10 U 010 U 01 )* to a DFA? My question about relations is what exactly does a relation mean, I know that R C A X B but I'm not really sure what it means.

Answer 1

In regular expression the symbol $\cup$ means essentially or: the regular expression $01\cup 10$, for instance, is $01$ or $10$ and is matched by both $01$ and $10$. If $S$ is the set of strings matching a regular expression $\sigma$, the strings that match $\sigma^*$ are the ones that can be formed by concatenating any finite number of strings in $S$. If $\sigma$ is the regular expression $01\cup 10$, the set $S$ has just two members: $S=\{01,10\}$. What can you get by concatenating $01$’s and $10$’s? You can get $\epsilon$, the empty string, by concatenating $0$ copies of $01$ or $10$. You can get $01$ and $10$. By concatenating two things you can get $0101,0110,1001$, and $1010$. In fact $(01\cup 10)^*$ matches an infinite number of different strings:

$$\begin{align*} &\epsilon,\\ &01,10,\\ &0101,0110,1001,1010,\\ &010101,010110,011001,011010,100101,100110,101001,101010, \end{align*}\tag{1}$$

and so on. In the regular expression $0(01\cup 10)^*1$ this is sandwiched between a $0$, which is matched only by $0$, and a $1$, which is matched only by a $1$; the strings that match this regular expression are those that you get when you put a $0$ in front of and a $1$ after each string in $(1)$:

$$\begin{align*} &01,\\ &0011,0101,\\ &001011,001101,010011,010101,\\ &00101011,00101101,00110011,00110101,01001011,01001101,01010011,01010101,\\ &\;\vdots \end{align*}$$