RE: Odd length string over { 0, 1} that contains exactly two 0's [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

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 0s.

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 0s it gets really messed up. I can only see that I can use * with 1 only since # of 0s are limited to 2. But if I do (11)* , I can't get the permutation of 0s inside the 1s. (e.g. can't get 10101 with (11)*).

What I know:

1. Only 1s can use *
2. In the regex only two 0s 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.

Answer 1

Regular Language over {0, 1} that is a set of all odd length strings that contain exactly two 0.

What this language means?

Note language string can be consist of two 0 and any number of 1 such that total length of string is odd. There is no other restriction. 1 and 0 an appear in any order and in any pattern.

As we know even + odd = odd. So in string is consist of at least three length and odd number of 1 because number of 0 in string is two.

So regular expression should be something like: A 0 B 0 C , where A, B, C, are substrings consist of only 1 and total number of 1 in A, B, C is odd, hence all can't be ^ (nul) in a expression.

Now because total number of 1 in A, B, C = odd, so it can be something like: either(1) two even and one odd or (2) all three are odd.

Note: a odd length string can't be null.

Regular Expression:

1(11)*01(11)*01(11)* + 1(11)*0(11)*0(11)* + (11)*01(11)*0(11)* + (11)*0(11)*01(11)*
// all odd             A odd, B C even       B odd, A C even     A B even, C odd