The Gateway to Computer Science Excellence
+13 votes
1.4k views
Give a regular expression over the alphabet $\{0, 1\}$ to denote the set of proper non-null substrings of the string $0110$.
in Theory of Computation by Boss (30.8k points)
recategorized by | 1.4k views
+14
I think regular expression would be:(0+1+01+10+11+011+110)
+1
eps won't be included as eps is null string.
0

what is the proper meaning of non null sub string ?

0
is 0110 a substring of 0110 or not?
0
0110 is not a proper substring of 0110 but it is a substring. So eps and 0110 are excluded.

5 Answers

+11 votes
Best answer
$0,1,01,10, 11 ,011 , 110 \\ \therefore RE : (0+1+01+10+11 +011 +110 )\\ \epsilon \ and \  0110 \  are \ not \ part \ of \  RE \ because \ of \ NON-NULL \ and \ PROPER! $
by Boss (11.9k points)
selected by
0
can we use CYK algorithm here , event though it is  given REGULAR.

but every REGULAR is CFL ,can we use CYK????? but it takes much more time
0
# of substring: $\dfrac{n(n+1)}{2}+1=11$

Remove $0110$ $\&$ $\epsilon$ string as they have asked only proper non-null sub-strings.

So let's write down 9 substrings:

$0,1,1,0:$

$01,11,10$

$011,110$

Some of them are repeating. Hence we have to remove them. Resulting us just with 7 sub-strings:

$0,1,01,11,10,011,110$
+6 votes
L = {0,1,01,11,10,011,110}

R.E = 0(ε+1+11) + 1(ε+0+1+10)
by Boss (16.4k points)
0
with above R.E we can also generate 011110 which is not a substring.

are you sure of your answer?
0
You can't generate 011110 from it. Try to make DFA , you will get it.
This R.E is same as the one given in the best answer but in succinct form.
0
oh! i misunderstood "+" sign in between of both expression and thought it is concatenation so end up deriving wrong string.🤔
+2 votes
$\varepsilon ^*0110\varepsilon ^*$
by Junior (667 points)
edited by
0 votes

0(E+1+11)+1(E+0+10)

by (181 points)
0
sub-string 11 cannot be accepted from your R.E.Substring 11 should be accepted by R.E.
–1 vote
Since we have to get only non NULL substrings, hence ∈ should bot be present.

(0 + 1) ( 0 + 1 + ∈) ( 0 + 1 + ∈)

Please correct me if i am wrong
by Active (4.4k points)
edited by
0
000 is produced by your RE, which isn't a substring.
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
50,737 questions
57,367 answers
198,500 comments
105,271 users