I just started learning about formal lang and automata theory, and recently learned about regex, so I don't know any complicated symbols, so please stick with basic symbols.

The question is: Write a regex for the following language over {0,1} that is a set of all odd length strings that contain exactly two 0's.

I've got the first part finished (the odd part), it should be:

(0+1)[(0+1)(0+1)]* ( + is the same as | (or) I believe, we learnt it as +)

However, when I think about having exactly two 0's it gets really messed up. I can only see that I can use * with 1 only since # of 0's are limited to 2. But if i do (11)* , I can't get the permutation of 0's inside the 1's. (e.g. can't get 10101 with (11)*).

What I know:

  1. Only 1's can use *
  2. In the regex only two 0's will be used
  3. The way to make odd length is to add an odd length to an even length (even length needs to have empty string within it's set)
  4. Odd length should not use * since 2 odd = even, so only even length can use *

For possible hints or answer, please use 0,1,+/|,*,(,) only. Some other expressions I will not be able to understand.


1 Answer 1


Hint. You did a good start, except maybe for (4). Note that $(11)^*1$ is a regular expression for the set of words of odd length (on the alphabet $\{1\}$). Does that help you?

Hint 2. Consider a word in your language. You know you have exactly two $0$ and hence your word is of the form $1^i01^j01^k$ for some $i, j, k \geqslant 0$ such that $i + j + k$ is an odd number.

Answer $(11)^*10(11)^*10(11)^*1 + (11)^*10(11)^*0(11)^* + (11)^*0(11)^*10(11)^* + (11)^*0(11)^*0(11)^*1$

  • $\begingroup$ what do u mean by except 4. 4 is saying if u kleene closure an odd length string, then you have rotation between even and odd every time. e.g. (111)* = 111, 111111, 111111111 which is odd, even, odd. $\endgroup$
    – LarsChung
    Sep 21, 2013 at 15:26
  • $\begingroup$ I only said "maybe (4)" because I was not sure whether you realized what I said about $(11)^*1$. This RE for odd length makes use of $*$, contrary to your statement "Odd length should not use *". $\endgroup$
    – J.-E. Pin
    Sep 21, 2013 at 16:15
  • $\begingroup$ If you read, I said I already figured out the odd part. Meaning I know I need to kleene closure on even length string (e.g. (11)*). (4) is stating that you can only use kleene closure on even length string because if you kleene closure on odd length string you can't get ONLY ODD LENGTH STRING requirement. I appreciate you replying to my question, but it doesn't help a single bit, you wrote what I have already figured out which is stated in the question. $\endgroup$
    – LarsChung
    Sep 22, 2013 at 7:25
  • $\begingroup$ Just so this doesn't confuse I'm saying you need to kleene closure even length + concatenate an odd length string. (e.g. (11)*1, (1111)*1, (11)*111) $\endgroup$
    – LarsChung
    Sep 22, 2013 at 7:26
  • $\begingroup$ I have added a second hint to my first answer. Does it help you? $\endgroup$
    – J.-E. Pin
    Sep 22, 2013 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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