2
$\begingroup$

I had an exam on Theory of Computation, and one of the questions was to write down a regular expression for the language over $\{0,1\}$ consisting of all words containing at least one 1. My answer was:

$$ 0^* 1 0^* (0^* 1 0^*)^* \, . $$

My teacher gave me one mark out of 5, yet I can't find a possible string that will give false output here! His answer, which was $(0+1)^*1(0+1)^*$, was better, but mine works as well, I believe.

Is my answer correct?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Your answer is definitely not wrong. The 3rd 0* is a bit useless, but that's hardly a reason to penalize. $\endgroup$
    – Karolis Juodelė
    Commented Dec 7, 2014 at 14:17
  • $\begingroup$ Zaid, did you speak to your teacher after reading the answer here? $\endgroup$
    – Hendrik Jan
    Commented Dec 15, 2014 at 17:31
  • $\begingroup$ @HendrikJan no he haven't showed up since then! $\endgroup$
    – zaid shawahin
    Commented Dec 17, 2014 at 13:13

1 Answer 1

Reset to default
4
$\begingroup$

Your answer is correct. $0^*1$ matches the portion up to the first $1$. After that, any subsequent $1$s may have any number of $0$s between them.

There are slightly simpler regular expressions for the same language. For example,

$$0^*10^*(0^*10^*)^* \ \equiv\ 0^*10^*0^*(10^*)^*\ \equiv\ 0^*10^*(10^*)^*\,.$$

You could also observe that a string with at least one $1$ is formed of some number of initial $0$s, followed by the first $1$, followed by anything else, leading to $0^*1(0+1)^*\!$, which is arguably slightly simpler than the teacher's solution.

However, you should consider that you probably lost marks for reasons other than the teacher mistakenly thinking that you were wrong. I wouldn't allocate five marks just for writing down a simple regular expression. To me, that would be either a one-mark question (one mark for right, none for wrong) or a two-mark question (two marks for right, one for being close and maybe missing a corner case, none for wrong). For five marks, I'd expect an explanation of why the regular expression does what it's supposed to do.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I agree with this complete analysis. One quality criterion is that explaining the regular expression is simple, or better that a correctness proof is simple. Another criterion could be the star height which is a measure of complexity of the regular expression. Your solution has star height 2 (because you have a star over a subexpression that already has one), when other solutions have star height one. But knowing this can hardly be expected from beginners. Possibly you teacher misread the answer ... can happen. Can you ask what you did wrong? $\endgroup$
    – babou
    Commented Dec 7, 2014 at 14:54
  • $\begingroup$ The second representation in your answer cannot generate 111 string!!!. You need a kleen star there too $\endgroup$
    – Rishabh Jain
    Commented Sep 9, 2018 at 18:01
  • $\begingroup$ Thanks, Rishabh -- you're absolutely right. I've fixed that, as you suggested. $\endgroup$
    – David Richerby
    Commented Sep 9, 2018 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.