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 ?


1 Answer 1


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)) $$

  • $\begingroup$ Hardly the "concise regular expression" the OP asked for. In the distant past, my doctorial adviser said to me "some things are just complicated". $\endgroup$ Mar 1, 2022 at 15:22
  • $\begingroup$ A finite state machine is often easier. $\endgroup$
    – gnasher729
    Mar 1, 2022 at 17:04
  • $\begingroup$ 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 $\endgroup$
    – Russel
    Mar 1, 2022 at 23:42

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.