# Is the difference between two regular expressions a new regular expression?

Let say the following:

Given Ax and Bx two literals which represent POSIX regular expressions.

Let def A as the set of literals that match Ax. The same def for B.

Using relative complement operation, is there always regular expression for $A/B$ set, for every pair of Ax,Bx?

I attach an example:

Ax := a.*
Bx := a.*b$// The difference A/B would be Cx := a.*[^b]$

• Have you checked the closure properties of regular languages? – adrianN Oct 24 '17 at 14:51
• No, I didn't. That comment answers directly this question. Can you post that information as an answer? – lilezek Oct 24 '17 at 15:31

While regular languages are indeed closed under set difference, there is no nice way of effecting this operation on regular expressions. Indeed, even regular expression complementation can result in an exponential blow-up. One simple example is the regular expression $r_n = \sum_{i=1}^n (\sum_{j \neq i} \sigma_j)^*$ over the alphabet $\Sigma = \{\sigma_1,\ldots,\sigma_N\}$, which corresponds to all words which do not have all letters of the alphabet. This regular expression has polynomial length (in $n$), but every regular expression for $\Sigma^* \setminus L(r_n)$ has exponential length.
• What is $L(r_n)$? May you explain why is it exponential in size? – lilezek Nov 24 '17 at 17:20
• The language of $r_n$. – Yuval Filmus Nov 24 '17 at 17:21