Converting to regular expressions

2.7k Views Asked by At

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

2

There are 2 best solutions below

9
On BEST ANSWER

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

4
On

$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 ;-)