How do I represent "Any string except for .... "

Question

I'm trying to solve a regex where the given alphabet is Σ={a,b}

The first expression is:

L1 = {a^2n b^(3m+1) | n >= 1, m >= 0}

which means the corresponding regex is: aa(a)*b(bbb)*

What would be a regex for L2, complement of L1? Is it right to assume L2 = "Any string except for aa(a)b(bbb)"?

I have to represent L2 = L1 L stand for the complement of L; Assume that alphabet Σ={a,b} — Azr4el, Apr 11 '16 at 08:07

Adrien Brunelat · Answer 1 · 2016-04-11T13:16:48.363

3

First, in my opinion, the regex for L1 = {a^2n b^3m+1 | n>=1, m>=0} is NOT what you gave but is: aa(aa)*b(bbb)*. The reason is that a^2n, n > 1 means that there are at least 2 a and a pair number of a.

Now, the regular expression for "Any string except for aa(aa)*b(bbb)*" is:

^(?!^aa(aa)*b(bbb)*$).*$

more details here: Regex101

Explanations

aa(a)*b(bbb)* the regex you DON'T want to match
^ represents begining of line
(?!) negative lookahead: should NOT match what's in this group
$ represents end of line

EDIT

Yes, a complement for aa(aa)*b(bbb)* is "Any string but the ones that match aa(aa)*b(bbb)*".

Now you need to find a regex that represents that with the syntax that you can use. I gave you a regex in this answer that is correct and matches "Any string but the ones that match aa(aa)*b(bbb)*", but if you want a mathematical representation following the pattern you gave for L1, you'll need to find something simpler.

Without any negative lookahead, that would be:

L2 = ^((b+.*)|((a(aa)*)?b*)|a*((bbb)*|bb(bbb)*)|(.*a+))$

Test it here at Regex101

Good luck with the mathematical representation translation...

edited Apr 11 '16 at 13:16

answered Apr 11 '16 at 08:06

Adrien Brunelat

4,492
4
29
42

Is it right to represent ^((?!aa(a)*b(bbb)*))*$ in computation theory way? – Azr4el Apr 11 '16 at 08:12
@Tim007 a negative lookahead, check this out: http://stackoverflow.com/questions/406230/regular-expression-to-match-line-that-doesnt-contain-a-word – Adrien Brunelat Apr 11 '16 at 08:16
1

@Azr4el What? You wanted a regex that matches any string that didn't match the given regex, here's one. I don't know about computation theory way... – Adrien Brunelat Apr 11 '16 at 08:20
@Azr4el Maybe that's not what you wanted, if so please edit your question to make it more clear. – Adrien Brunelat Apr 11 '16 at 08:24
@adrien-brunelat i don't ask about negative lookahead or regex stuff and things : D, just because your answer doesn't make sense to Azr4el's question. – Tim007 Apr 11 '16 at 08:31
You question didn't make sense. But with the new edit, I get what you want and I'm working on it. – Adrien Brunelat Apr 11 '16 at 08:33
@Azr4el Hmm... You just validated my answer, but it doesn't match with your last edit. What is happening? – Adrien Brunelat Apr 11 '16 at 08:36
@AdrienBrunelat it was a misclick Im sorry. – Azr4el Apr 11 '16 at 08:37
@Azr4el are you allowed to use some kind of `OR` syntax in the L2 mathematical expression? – Adrien Brunelat Apr 11 '16 at 08:54
@Azr4el And what about a `NOT`? – Adrien Brunelat Apr 11 '16 at 09:57
@adrien-brunelat your regex will fail in `aabb` that should matches by L2 but not L1 – Tim007 Apr 11 '16 at 10:39

Tim007 · Answer 2 · 2016-04-11T10:53:51.823

The first expression is:

L1 = {a^2n b^(3m+1) | n >= 1, m >= 0}

Regex for L1 is:

^aa(?:aa)*b(?:bbb)*$

Regex demo
Input

a
b
ab
aab
abb
aaab
aabb
abbb
aaaab
aaabb
aabbb
abbbb
aaaaab
aaaabb
aaabbb
aabbbb
abbbbb
aaaaaab
aaaaabb
aaaabbb
aaabbbb
aabbbbb
abbbbbb
aaaabbbb

Matches

MATCH 1
1.  [7-10]  `aab`
MATCH 2
1.  [30-35] `aaaab`
MATCH 3
1.  [75-81] `aabbbb`
MATCH 4
1.  [89-96] `aaaaaab`
MATCH 5
1.  [137-145]   `aaaabbbb`

Regex for L2, complement of L1

^aa(?:aa)*b(?:bbb)*$(*SKIP)(*FAIL)|^.*$

Explanation:
^aa(?:aa)*b(?:bbb)*$ matches L1
^aa(?:aa)*b(?:bbb)*$(*SKIP)(*FAIL) anything matches L1 will skip & fail
|^.*$ matches others that not matches L1
Regex demo
Matches

MATCH 1
1.  [0-1]   `a`
MATCH 2
1.  [2-3]   `b`
MATCH 3
1.  [4-6]   `ab`
MATCH 4
1.  [11-14] `abb`
MATCH 5
1.  [15-19] `aaab`
MATCH 6
1.  [20-24] `aabb`
MATCH 7
1.  [25-29] `abbb`
MATCH 8
1.  [36-41] `aaabb`
MATCH 9
1.  [42-47] `aabbb`
MATCH 10
1.  [48-53] `abbbb`
MATCH 11
1.  [54-60] `aaaaab`
MATCH 12
1.  [61-67] `aaaabb`
MATCH 13
1.  [68-74] `aaabbb`
MATCH 14
1.  [82-88] `abbbbb`
MATCH 15
1.  [97-104]    `aaaaabb`
MATCH 16
1.  [105-112]   `aaaabbb`
MATCH 17
1.  [113-120]   `aaabbbb`
MATCH 18
1.  [121-128]   `aabbbbb`
MATCH 19
1.  [129-136]   `abbbbbb`

How do I represent "Any string except for .... "

2 Answers2