I found this given problem as follows:

Write a regular expression where all strings in which every substring 000 appears after every 1.

Now, I also found the answer from Illinois university study material which is available online. The given answer is as follows:


However, I think this is not the correct answer as the RE can generate the given strings as 1, 10, 1010010 and so many. So the RE is not properly justified to the given problem.

Please, help me to get the correct information. Thanks for your kind consideration.


1 Answer 1


The formulation

every substring 000 appears after every 1

is extremely ambiguous. However, given the proposed solution, here is how we are supposed to interpret it. Let $w$ and $x = x_0 \ldots x_{m-1}$ be words. We say that $x$ occurs in $w$ at position $i$ if $$w_i w_{i+1} \ldots w_{i+m-1} = x_0 x_1 \ldots x_{m-1}.$$ The language in question consists of all words $w$ such that if $1$ occurs in $w$ at position $i$ and $000$ occurs in $w$ at position $j$, then $i < j$. This means that after the first time that $000$ occurs, the word consists only of $0$s. Therefore we can break words in the language into two parts: the first part doesn't contain $000$ at all, and the second part, which is optional, contains $000$ followed by any number of $0$s.


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.