GATE CSE 1987 | Question: 10d

Question

Give a regular expression over the alphabet $\{0, 1\}$ to denote the set of proper non-null substrings of the string $0110$.

Comments

what is the proper meaning of non null sub string ?

---

is 0110 a substring of 0110 or not?

---

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

Answer 1

$0,1,01,10, 11 ,011 , 110$

$ \therefore \text{RE} : (0+1+01+10+11 +011 +110 )$

$\varepsilon$ and $0110$ are not part of RE because of NON-NULL and PROPER substring requirement.

Comments

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

---

# 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$

Answer 2

L = {0,1,01,11,10,011,110}

R.E = 0(ε+1+11) + 1(ε+0+1+10)

Comments

with above R.E we can also generate 011110 which is not a substring.

are you sure of your answer?

---

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.

---

oh! i misunderstood "+" sign in between of both expression and thought it is concatenation so end up deriving wrong string.🤔

Answer 3

$\varepsilon ^*0110\varepsilon ^*$

Answer 4

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

Comments

sub-string 11 cannot be accepted from your R.E.Substring 11 should be accepted by R.E.