# Converting to regular expressions

I am really not sure about the following problem, I tried to answer it according to conversion rules the best I can. I was wondering if someone can give me some hints as to whether or not I am on the right track.

Many thanks in advance.

Convert to Regular Expressions

L1 = {w | w begins with a 1 and ends with a 0.} = 1E*0

L2 = {w | w contains the substring 0101} = E*0101E*

L3 = {w | the length of w does not exceed 5} = EEEEE

L4 = {w | every odd position of w is a 1} = (E*=1 intersection E*E*)

L5 = { w | w contains an odd number of 1s, or exactly 2 0s. } = (E)* U (E=0)*2

-

As for $L_1$ you are right, if you would like a more generic approach, it would be $1E^* \cap E^* 0$ which indeed equals $1E^*0$. The thing to remember is that conjunction "and" can be often thought of as intersection of languages.

Regarding $L_2$, it is also ok.

Your answer to $L_3$ is wrong, $EEEEE$ means exactly 5 symbols, where "does not exceed $5$ allows for much more, e.g. empty string. One way to achieve this is $\{\varepsilon\} \cup E \cup EE \cup EEE \cup E^4 \cup E^5$ or shorter $\bigcup_{k=0}^{5}E^k$.

In $L_4$ I do not understand your notation $E^*=1$. Also $E^*E^*$ equals $E^*$, that is, if you join two arbitrary strings of any length you will get just an arbitrary string of some length, on the other hand $(EE)^*$ would be different, in fact the length of $(EE)^*$ has to be even. Observe:

\begin{align} \{\varepsilon\} = E^0 = (E^2)^0 \\ EE = E^2 = (E^2)^1 \\ EEEE = E^4 = (E^2)^2 \\ EEEEEE = E^6 = (E^2)^3 \\ EEEEEEEE = E^8 = (E^2)^4 \end{align}

$$\{\varepsilon\} \cup EE \cup EEEE \cup \ldots = (E^2)^0 \cup (E^2)^1 \cup (E^2)^2 \cup \ldots = (E^2)^*$$

Taking this into account, strings which contain $1$ on their odd positions are build from blocks $1\alpha$ for $\alpha \in E$ (I assume that first position has number 1) or in short form $1E$. To give you a hint, $(1E)^*$ would be a language of strings of even length with $1$ on odd positions. Try to work out the expression for any length.

$L_5$ could be better. Two $0$s should be $1^*01^*01^*$ or shorter $(1^*0)^21^*$. Four zeros would be $(1^*0)^41^*$, and using the example from $L_4$ try to find the correct expression for odd number of 1s. Some more hints: as "and" often involves intersection $\cap$, "or" usually ends up being some union $\cup$.

Hope this helps ;-)

-
+1 thank you very much, very helpful! :) I am trying to work on L4, but am having a hard time working out the case where it may end with an odd character where the odd character is 1. For L4, since empty string is part of every alphabet, by saying (1E)*, doesn't that take care of the possibility of the string ending with on an odd character 1, where the even character is empty string? –  Epsilon Jan 25 '13 at 16:17
Something like: (1E)* U (1 U {empty set})* –  Epsilon Jan 25 '13 at 16:24
And for L5: (00 U 1*001* U 1*00 U 1*01*0 U 01*01* U 001*) U ((1E)* U 1 U {e})) ........ because its asking for exactly two zeros OR an odd number of 1's. –  Epsilon Jan 25 '13 at 16:35
@MHZ: You already know that $(1E)^*$ will give you all words of $L_4$ of even length. The other words of $L_4$ have the form $(1E)^*1$. Thus, $(1E)^*\cup(1E)^*1$ works. Alternatively, you can factor it: $(1E)^*(\lambda\mid 1)$. –  Brian M. Scott Jan 25 '13 at 16:54
Thank you for the clarification! What does this: λ symbolize? –  Epsilon Jan 25 '13 at 16:56

$L3$ is wrong, what you give is all of length exactly 5.

$L4$ should be something like $(1E)^*(1|\epsilon)$

$L5$ is the union of two branches: Odd number of 1, exactly 2 0. Left as an exercise to the reader ;-)

-
Thank you, I appreciate the suggestions. L3 = empty set U E U EE U EEE U EEEE U EEEEE haha;) –  Epsilon Jan 25 '13 at 15:12
Can you please explain how you got the expression in L4? –  Epsilon Jan 25 '13 at 15:14
@MHZ, need 1E1E1..., and it could end ...E or E1. Add a dash of RE experience as a long-time vi(1) user in Unix ;-) –  vonbrand Jan 25 '13 at 16:06
Something like: (1E)* U (1 U {empty set})* –  Epsilon Jan 25 '13 at 16:38