Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Let's say our alphabet is 0 and 1.
How would you approach writing a regex to generate a language of words that do NOT contain 101.
The only regex operators allowed are concatenation , star * and OR |.
I am stuck now and I want to know if anybody has an idea.
If a string does not contain $101$, then every $10$ either terminates the string or is followed by $0$. So if $r$ is a regular expression for all strings not containing $10$, then a regular expression for all strings not containing $101$ is $$ (r100)^*r(10+\epsilon). $$ You take it from here. Note that there are also other solutions.
Complementing a regular expression can be a very costly operation. For example, the set of strings over $\{1,\ldots,n\}$ not containing all symbols has a regular expression of length $O(n^2)$ (exercise), but its complement requires a regular expression of exponential size $\Omega(2^n)$. This follows from the "fooling set" lower bound on NFAs, and the fact that regular expressions can be converted into NFAs with constant multiplicative overhead.
A fooling set for a language $L$ is a collection of pairs $(x_i,y_i)$ such that $x_iy_i \in L$ but for $i \neq j$, either $x_iy_j$ or $x_jy_i$ is not in $L$. If $L$ has a fooling set of size $n$ then every NFA for $L$ has size $n$ (exercise). In the case of all strings over $\{1,\ldots,n\}$ containing all symbols, there is a fooling set of size $2^n$: $\{(S,\overline{S}) : S \subseteq \{1,\ldots,n\}\}$, where we identify a set of symbols with the word containing these symbols in order.
