664 views

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 \}$

0

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

+2
@sourav
it is not accepting 11011011

L is regular because there are finite automata exist ofr this language.
We can not do comparission by using FA because it does not have memory so language is  not regular.

1