1
$\begingroup$

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]$
$\endgroup$
2
  • 1
    $\begingroup$ Have you checked the closure properties of regular languages? $\endgroup$ – adrianN Oct 24 '17 at 14:51
  • $\begingroup$ No, I didn't. That comment answers directly this question. Can you post that information as an answer? $\endgroup$ – lilezek Oct 24 '17 at 15:31
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What is $L(r_n)$? May you explain why is it exponential in size? $\endgroup$ – lilezek Nov 24 '17 at 17:20
  • 1
    $\begingroup$ The language of $r_n$. $\endgroup$ – Yuval Filmus Nov 24 '17 at 17:21
4
$\begingroup$

Regular languages are closed under relative complement. Since regular expressions encode exactly the regular languages, you can always find a regular expression that matches the relative complement of two other regular expressions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.