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.


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$

| cite | improve this answer | |
  • $\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 '13 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 '13 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 '13 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 '13 at 7:26
  • $\begingroup$ I have added a second hint to my first answer. Does it help you? $\endgroup$ – J.-E. Pin Sep 22 '13 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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