ISI2013-PCB-CS-4b

Question

Write a regular expression for all strings of $0$’s and $1$’s in which the total number of $0$’s to the right of each $1$ is even. Justify your answer.

Comments

0*(1(00)*)*?????

---

0*(1(00)*)*

I got the same and seems correct. 

Answer 1

Here Total no. of $0$'s to the right of each $1$'s should be even. So, to the left side of every $1$'s no. of $0$'s can be anything.

$L=\{ \epsilon ,0,00,000,01,011,0111,1,11,111,1111,100,10000,100100,10010000...................\}$

Hence,

$\mathbf{R.E.=0^*(1+00)^*= 0^*(1(00)^*)^* = 0^*(1+(00)^*)^* =0^*(1^*+(00))^* = 0^*(1^*+(00)^*)^*}$

Comments

@LeenSharma

can we have like

$(1(00)^*)^* + 0^* + 0^*1^*$

---

Satbir Check for string 0100.

---

How can we write $0^*(1+00)^*$. This Regular Expression will also generate 1,11,111... which should not be accepted. I think only $0^*(1(00)^*)^*$ and it's various other forms will work.

Answer 2

I feel the question is similar to this.

As far as I can think of,

$0^{*}(1(00)^{*})^{*}$

should be able to generate the strings of this language. 

Answer 3

I tried making an FSM and then reducing it to get 0*1(1 + 00)*, which accepts all legal strings.

Comments

your FSM in the first step is already minimized and is generating o*1(1+00)*. Why are you unnecessarily adding epsilon moves and removing trap state, which is indeed giving you more states that first fsm. You can simply reduce it to 3 states by just ignoring trap state in nfa.

---

I was formally applying the algorithm to reduce, not a big deal.

Answer 4

Simple logic:

(you may draw the corresponding DFA, if that approach is more suitable for you, as given in the picture by @mohitjarvissharma)

For $\#1's \ge 1$ Regular Exp : $0^*1(1+00)^*$

For $\#1's = 0$ Regular Exp : $0^*$

Combining them : $0^*1(1+00)^* + 0^* = 0^*(1+00)^* $ 

This is the simplest interpretation of the Regular Expression, it can be further represented as (all are given in @LeenSharma 's answer):
$ 0^*(1^*+00)^*$ or $ 0^*(1+(00)^*)^*$ or  $ 0^*(1^*+(00)^*)^*$ or $ 0^*(1(00)^*)^*$

All of the above are valid!