Regular expression of $L = \{w \in \{0, 1\}^* \mid w \text{ does not contain $111$}\}$

Question

I'm trying to find regular expression of $L = \{w \in \{0, 1\}^* \mid w \text{ does not contain $111$}\}$. I think there are many information about regular expression that does not contain the substring $110$. but I think $111$ is more difficult to find. can anybody help?

Answer 1

Everywhere you see a $1$ in this string, it is either

• At the end,

• followed by a $0$, or

• followed by $10$.

Therefore, strings in this language are built out of copies of $0$, $10$, and $110$, possibly with an extra $1$ at the end. Can you use this to build an RE?

Answer 2

Use the Arden's theorem.

Answer: (0+10+110)*(€+1+11) This is probably the minimal regexp. Or maybe it can get minimised.

Details.

DFA Delta moves. Or transitions.

Qo = {A} initial state. N = {A, B, C, D(dead state) } All states

d(A, 0) = A d(A, 1) = B

d(B, 0) = A d(B, 1) = C

d(C, 0) = A d(C, 1) = D

A=A0+B0+C0 B=A1 C=B1 D=C1

Solve for A then B then C.

Note if R = RP + Q Then, R = QP* Arden's theorem.