Regular expression theory

Question

I have a little problem with RE theory.

Given an alphabet {0, 1}, I have to create a regular expression that matches all string that does NOT contain the substring 111.

I'm not able to get the point, also for simplier substring like 00.

Edit: The solution must contains only the three standard operation: concatenation, alternation, kleene star, as you can see in the wiki link

Thank you.

Answer 1

As far as I understand, the language you want to regexify is not allowed to contain three or more consecutive 1's. Such a regexp could be (110|10|0*)*|1|11|0*1|0*11

Answer 2

How about this:

{ε|1}{ε|1}{ε|{0{ε|1}{ε|1}}*}

Answer 3

Back in the days when we didn't have the ?! negative lookahead facility I would use a negation match. So for grep I would

grep -v (pattern I'm searching for) someFile.txt

which would give the lines in the file that don't contain the pattern.

In perl I would use the

!~ 

negation matcher rather than the usual

=~ 

I don't know which regex variant you are using, but I'm struggling to see a way to solve your problem without either an overall negation or a ?! negative lookahead.

matcher.