Modified GATE2014-2-36

Question

Let $L=\left \{ w\in\{0,1\}^* | \text{number of occurances  of }(110)=\text{number of occurances  of}(011) \right \}$

What is $L$?

---

I think $L$ is regular .

Regular expression is -:

$L=\left \{ 0^{*}+1^{*}+\left ( \left ( \varepsilon +0+1 \right )  \left ( \varepsilon +0+1 \right ) \right ) + 0^{*}\left ( 0110 \right )^*0^{*}+1^* \left ( 11011 \right )^{*}1^{*}  \right \}$

Comments

See,

number of (110)=number of (011)

if x=110 and y=001

or   number of (x)=number of (y) .// Here it is 1 comparision,so we need a stack to do it.

So, it cannot be regular

secondly,

Regular expression is -:

L={0∗+1∗+ ((ε+0+1)(ε+0+1))+0∗(0110)∗0∗    +1∗(11011)∗1∗} is not correct 

     {ε  + 1 +(   (       1)  (        0 )  +            ε  +           ε    }        = 110

 i.e (number of (110) !=number of (011)

i.e :    110  or ... we can generate many strings which are not in original L

---

@sourav
it is not accepting 11011011

Answer 1

I stand to be corrected but here is what i think

L1 : Set of all strings where number of 110 is atleast as much as number of 011 is regular

L2 : Set of all strings where number of 011 is atleast as much as number of 110 is regular(I am almost sure this is the case but this is the part where i am not very confident)

L3 = L1 $\bigcap$ L2 : Set of all string where number of 011 equals number of 110 will be regular as regular languages are closed under intersection

Ref: https://gateoverflow.in/1995/gate2014-2-36 to see why L1 and L2 are regular.

Comments

What will be the regular expression for L3 ?

Answer 2

L is regular because there are finite automata exist ofr this language.

Comments

Yes l is regular.