0
$\begingroup$

I'm working on homework for my formal languages and automata course. The text we are using is the first edition of Hopcroft and Ullman (1979).

Specifically, I'm unsure how to justify that my regular expression for exercise 2.10 (c) is correct. The question asks for a regular expression for the set of all strings not containing the substring 101 (over the alphabet $\{0, 1\}$). Additionally, it asks for justification that the regular expression you write is correct.

I came up with the regular expression $$0^*1^*0^* + (1 + 00 + 000)^* + 0^+1^+0^+.$$

As for the justification, what exactly are they looking for?

Improve this question
$\endgroup$
4
  • $\begingroup$ "justifying" is not necessarily "proving". What they are looking for depends on the standards of your school/class/staff. It can range from a hand-wavy explanation of why your regexp indeed generate exactly the claimed language, to a details formal proof that this is indeed the case. What answer do you expect? $\endgroup$
    – Ran G.
    Commented Feb 8, 2014 at 23:49
  • $\begingroup$ Another tip: can your regexp generate $010010$? And also note that your 3rd term is included in the first term. $\endgroup$
    – Ran G.
    Commented Feb 9, 2014 at 2:08
  • $\begingroup$ The answer to this question is covered by cs.stackexchange.com/q/1331/755 and cs.stackexchange.com/q/2016/755. $\endgroup$
    – D.W. ♦
    Commented Feb 10, 2014 at 3:27
  • $\begingroup$ cs.stackexchange.com/q/156003/755 $\endgroup$
    – D.W. ♦
    Commented Dec 7, 2022 at 19:26

0

Reset to default