The Gateway to Computer Science Excellence
+6 votes
796 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 \}$

in Theory of Computation by Boss | 796 views
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

2 Answers

0 votes

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.

by
edited by
0
What will be the regular expression for L3 ?
–1 vote
L is regular because there are finite automata exist ofr this language.
by Junior
0
Yes l is regular.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,215 questions
60,009 answers
201,234 comments
94,696 users