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?

$\endgroup$
  • 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ė Dec 7 '14 at 14:17
  • $\begingroup$ Zaid, did you speak to your teacher after reading the answer here? $\endgroup$ – Hendrik Jan Dec 15 '14 at 17:31
  • $\begingroup$ @HendrikJan no he haven't showed up since then! $\endgroup$ – zaid shawahin Dec 17 '14 at 13:13
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.

$\endgroup$
  • 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 Dec 7 '14 at 14:54
  • $\begingroup$ The second representation in your answer cannot generate 111 string!!!. You need a kleen star there too $\endgroup$ – Rishabh Jain Sep 9 '18 at 18:01
  • $\begingroup$ Thanks, Rishabh -- you're absolutely right. I've fixed that, as you suggested. $\endgroup$ – David Richerby Sep 9 '18 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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