3
$\begingroup$

I've come across this problem in my studies, and I've abstracted it to the more general case here.

Given a finite alphabet, what is a regular expression that matches all strings over the alphabet, except one particular finite substring?

As an example:

Given $\Sigma = \{a, b, c\}$

What is a regular expression that matches all of $\Sigma$ except the substring $ ba$?

What I really want is simply $\Sigma^* - ba$.

$\endgroup$
  • 1
    $\begingroup$ In your question you state "except one particular finite sub string", where "sub" suggests that you are interested in $\Sigma^* - \Sigma^* ba \Sigma^*$ instead? $\endgroup$ – Hendrik Jan Sep 12 '13 at 13:21
  • $\begingroup$ @HendrikJan Yes, that is what I rather meant to say, sorry about that. $\endgroup$ – user2666425 Sep 12 '13 at 21:12
  • 1
    $\begingroup$ What have you tried? Have you looked at any comparable example, e.g. via regular-expressions? Can you give an NFA and convert it? $\endgroup$ – Raphael Sep 16 '13 at 7:18
4
$\begingroup$

Just draw the minimal complete DFA accepting your string, change the final states to get the complement and now convert this new DFA to a regular expression.

In your case, you will get $\mathcal{A} = (Q, A, \cdot, 1, F)$ with $Q = \{0, 1, 2, 3\}$, $A = \{a, b, c \}$, $F = \{3\}$ and $1 \cdot b = 2$, $2 \cdot a = 3$ and $q \cdot x = 0$ for all other transitions. Thus the automaton for the complement is $\mathcal{A}' = (Q, A, \cdot, 1, F')$ with $F' = \{0, 1, 2\}$.

Converting $\mathcal{A}'$ to a regular expression gives $$ 1 + b + (c + bc + baA)A^* $$

$\endgroup$
  • $\begingroup$ I have not seen this notation of $1$ in a regular expression. And is $+$ equivalent to the union operation? $\endgroup$ – user2666425 Sep 12 '13 at 21:14
  • 1
    $\begingroup$ This is the algebraic notation (quite common) for a regular expression. Union is denoted by + and 1 denotes the empty word, which is the neutral element for the concatenation product: for all words u, 1u = u = u1. $\endgroup$ – J.-E. Pin Sep 12 '13 at 23:09
  • $\begingroup$ In the regular expression you gave, it contains '..$baA$'. So doesn't this set (or language) represented by this regular expression obviously contain strings with ba as a substring? Furthermore, if you're doing $A^*$, you will get $ba$, $bba$, will you not? $\endgroup$ – user2666425 Sep 12 '13 at 23:43
  • $\begingroup$ By definition, $A = a + b + c$ and hence $baA = baa + bab + bac$. Thus $baAA^*$ is the set of all words of the form $baau$, $babu$ or $bacu$ for some word $u$. None of these words is equal to $ba$. $\endgroup$ – J.-E. Pin Sep 13 '13 at 7:02
  • 1
    $\begingroup$ The last sentence of your question clearly states "What I really want is simply $\Sigma^*− ba$" and I tried to answer this question. If the question you had in mind was different, it would be better to ask another question. $\endgroup$ – J.-E. Pin Sep 13 '13 at 20:26
1
$\begingroup$

One way of finding such a regular expression is $$ \epsilon+a+b+c+aa+ab+ac+bb+bc+ca+cb+cc+(a+b+c)(a+b+c)(a+b+c)(a+b+c)^*. $$ There might be more succinct solutions, but this always works (for all finite languages).

$\endgroup$
  • $\begingroup$ I think OP means $\Sigma^*-\Sigma^*ba\Sigma^*$ as henric mentioned in his comment, otherwise as you write excluding that string is enough. $\endgroup$ – user742 Sep 12 '13 at 13:30
  • 1
    $\begingroup$ I don't see a "way" here, only a final result. $\endgroup$ – Raphael Sep 16 '13 at 7:18
  • 1
    $\begingroup$ @Raphael I'm sure you can generalize this. If the maximal word omitted is of length $\ell$, I'm listing all other words of length at most $\ell$, and add $\Sigma^{\ell+1} \Sigma^*$. $\endgroup$ – Yuval Filmus Sep 16 '13 at 15:01

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.