The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+6 votes
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 \}$

asked in Theory of Computation by Boss (15.9k points) | 664 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
L is regular because there are finite automata exist ofr this language.
answered by Active (1.1k points)
0 votes
We can not do comparission by using FA because it does not have memory so language is  not regular.
answered by (253 points)

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
49,811 questions
54,533 answers
188,417 comments
75,580 users