reset password
Author Message
BruceHan
Posts: 7
Posted 10:16 Apr 04, 2013 |

So I started on the assignment and I'm stumped on number 3.

 

Which of the following regular expressions denotes the set of all strings over the alphabet {0,1} that contains the substring010.

a. (1+0)*010(1+0)*
b. 0(1+0)* 1(1+0)* 0(1+0)*
c. (010)*

So I'm pretty sure it's a & c but there's no option for it on the assignment. Does that mean that I'm wrong about a,b, and c?

Last edited by BruceHan at 10:28 Apr 04, 2013.
jkelsey
Posts: 12
Posted 13:15 Apr 04, 2013 |

I agree. The correct answers include both a and c, do they not?

BruceHan
Posts: 7
Posted 13:47 Apr 04, 2013 |

The available answers are A, B, C, All of the Above, and None of the Above so I started second guessing myself. Lol.

jkelsey
Posts: 12
Posted 13:57 Apr 04, 2013 |

(1+0)*010(1+0)* contains the substring because it explicitly requires 010.

 

(010)* can contain the substring because the asterisk operator means that the sequence can appear 0 or more times. It also accepts the empty set. If it optionally accepts the empty set or 010, does that mean this is not a correct answer?

BruceHan
Posts: 7
Posted 14:23 Apr 04, 2013 |

Ahh!! Right you are! I totally forgot about the empty set! Thanks!

jkelsey
Posts: 12
Posted 14:31 Apr 04, 2013 |

Right. But my question is, since it accepts the empty set, does that mean it's wrong? I wouldn't think so, accept that there can only answer, according to Dr. Pamula.

BruceHan
Posts: 7
Posted 14:48 Apr 04, 2013 |

Yeah, I think it's wrong because the question wants all sets that contains the substring 010 and the empty set does not.

jkelsey
Posts: 12
Posted 16:12 Apr 04, 2013 |

The empty set does not, but the empty set is only a subset of the answer set, which contains at least the following:

{{}, {010},{010010},...}

Thus, 010 is a substring that exists in the answer set.

 

Maybe I'm missing something. I'll have to wait until I get home to check out the automata textbook.