# Regular expression of binary strings not containing $1011$ or $1101$ as substring

I tried to solve by explicitly writing strings of length $$2$$, $$3$$ and $$4$$ (other than $$1011$$ and $$1101$$), but it creates a lengthy regular expression. Can someone suggests underlying pattern that helps in writing concise regular expression ?

Denote your language by $$L$$. The words $$w$$ in the list below satisfy the following property: $$x \in L$$ iff $$wx \in L$$: $$0,(10)^+0, 11^+00$$ If a word doesn't start with any of these, then it must be of one of the following forms, where $$z$$ is some arbitrary word: $$\epsilon, (10)^*1,(10)^+,(10)^+11z,11^+,11^+0,11^+01z$$ The two cases involving $$z$$ are not in $$L$$. We conclude that an unambiguous regular expression for $$L$$ is $$(0+(10)^+0+11^+00)^*(\epsilon + (10)^*1 + (10)^+ + 11^+ + 11^+0)$$ or $$((10)^*0+11^+00)^*((10)^*(\epsilon+1)+ 11^+(\epsilon+0))$$

• Hardly the "concise regular expression" the OP asked for. In the distant past, my doctorial adviser said to me "some things are just complicated". Mar 1, 2022 at 15:22
• A finite state machine is often easier. Mar 1, 2022 at 17:04
• Finite state machine to regular expression usually leads to longer expressions and besides the problem is asking for the complement, which mostly will lead to writing down all paterns that works Mar 1, 2022 at 23:42