Good day, I come across this question on my textbook and would like to seek some help. In this question, I was asked to design a regular language that accept all binary string except for string that contains "1001", and I have never come across this type of questions before.
I know that the regular language for all binary string is 1 * 0 * 1 * 0 *(probably not the best one, but at least it works), and my initial thought was that I can just make sure that were always at least 3 0s in the middle, like 1 * 000+ 1 * 0 *, but quickly I realized that it would not work as it eliminated the strings like "101" as well.
Please give me some insight on solving this problem such as what the pattern is, thank you
One approach would be to find a finite automata that passes your regular expression.
Let your states be $\{A,B,C,D,F\},$ with $A$ the initial state, and $F$ the failure state. All other states are pass states.
From $A,$ a $0$ keeps you in state $A.$ For $1,$ $A\mapsto B.$
From $B,$ a $1$ maps to $B,$ and a $0$ maps to $C.$
From $C,$ a $1$ maps to $B$ and a $0$ maps to $D.$
From $D,$ a $0$ maps to $A,$ and $1$ maps to $F.$
From $F,$ both $0$ and $1$ map to $F.$
You are in state $F$ if we ever found $1001.$ In any other state, you have not seen $1001.$
We are in state $A$ if the string has no $1$s or there are at least $3$ zeroes after the last $1.$
You are in state $B$ if the string ends in a $1.$
You are in state $C$ and $D$ if the string ends in $10$ and $100,$ respectively.
The simple loops from $D$ to $D$ look like:
$$1|01|0000^*1$$
The simple loops from $A$ to $A$ are $0$ and $(1(1|01)^*000)$
We can get to $C$ and $D$ by appending $0$ and $00$ after the state $B.$
So the routes ending in $A$ are:
$$(0|(1(1|01)^*)000)^*\tag1$$
The routes ending in $B$ are $$(0|(1(1|01)^*)000)^*1(1|01)^*\tag2$$
The routes ending in $C$ and $D$ are, together, the map to $B$ followed by $(0|00)$:
$$(0|(1(1|01)^*)000)^*1(1|01)^*(0|00)\tag3$$
The final regular expression is quite messy, joining $(1),(2),$ and $(3).$
Another approach is to note that if the string has any ones, the state must got through $D.$ From $D$ we can end in $A,B,C,D$ if we append $\epsilon|0|00|0000^*=0^*$, wher $\epsilon$ is the empty string. So you get:
$$0^*|(0|(1(1|01)^*)000)^*1(1|01)^*0^*\tag4$$
You can come up with a better regular expression with some cleverness if you think of the binary strings as blocks of $a_{0}\geq 0$ zeros, then $a_1\geq 1$ ones, then $a_2\geq1$ zeros, … followed by $a_{2k-1}\geq1$ ones and $a_{2k}\geq 0$ zeros. Then the condition, “there is no $1001$“ is the same as $a_{2i}\neq 2$ for all $i=1,2,\dots,k-1.$
Then you get: $$0^*|0^*1(1|01|0000^*1)^*0^*$$
This means that after each $1$ we get either zero, one or more than two zeroes, except after the final $1,$ when we can get any number of $0$s.
You can simplify that one more time as:
$$0^*(1|01|0000^*1)^*0^*$$
But the most general way uses the automata. You get complicated results in general.
For example, excluding $10100,$ you get, after simplifying:
$$0^*\,\left((01)^*1|000^*1\right)^*\,\left((01)^*|(01)^*0|0^*\right)$$