1,348 views
7 votes
7 votes

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

2 Answers

1 votes
1 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.

edited by

Related questions

6 votes
6 votes
2 answers
3
Chhotu asked Nov 22, 2017
394 views
Refer check selected answer comments of https://gateoverflow.in/1995/gate2014-2-36.
0 votes
0 votes
2 answers
4
admin asked Apr 28, 2019
381 views
Let $B_{n} = \{a^{k}| \text{$k$ is a multiple of $n$}\}.$ Show that for each $n\geq 1,$ the language $B_{n}$ is regular$.$