Regular Expressions From Scratch, Part Three: Concatenation

Regular Expression: The Theory behind it!

Dan Sellers's WebLog — Sat, 04 Mar 2006 02:29:39 GMT

When it comes to validating input regular expression becomes a very important part of your security plan.&nbsp;...

Synesthesia » Links Roundup for 2006-02-21

Synesthesia » Links Roundup for 2006-02-21 — Wed, 22 Feb 2006 12:18:10 GMT

PingBack from http://www.synesthesia.co.uk/blog/archives/2006/02/22/links-24/

re: Regular Expressions From Scratch, Part Three: Concatenation

Andy — Thu, 09 Feb 2006 23:53:39 GMT

Shawn Cheng:

If a language L does not even have the empty string, then any concatenation with L could have no possible strings.

You could change your suggested example to this:

S = {a, b}
L = {e}
K = {e, b, bb, bbb, bbbb, ...}

In that case, it is true that LK = K
(LK = {w in S* such that w has the empty string followed by any number of bs})

If, however, L = {}, then LK = {}

Unless, of course, I'm wrong.

re: Regular Expressions From Scratch, Part Three: Concatenation

Shawn Cheng — Sun, 08 Jan 2006 18:50:52 GMT

Started to read this great series!

May I revise the example under the definition 6 a little bit to become the following:

S = {b}
L = {}
K = {e, b, bb, bbb, bbbb, …}

then

LK = {w in S* such that w has zero number of as followed by any number of bs}

then, we have LK = K. Agree? If yes, then the paragraph before the example is wrong.

Please correct me.

re: Regular Expressions From Scratch, Part Three: Concatenation

Eric Lippert — Thu, 05 Jan 2006 05:19:38 GMT

Yes, this would be an example of our more compact syntax. Clearly {e}* = {e} U {ee} U {eee} ... = {e}, so {e}* = {e}, so e*=e.

re: Regular Expressions From Scratch, Part Three: Concatenation

Matt — Thu, 05 Jan 2006 05:06:33 GMT

Good writing. So, based on what you say about the empty string, is it true that

e* = e

???

re: Regular Expressions From Scratch, Part Three: Concatenation

Rob Kennedy — Sat, 26 Nov 2005 08:31:42 GMT

Sembol,

The Kleene closure was definition 3, from last week:

http://blogs.msdn.com/ericlippert/archive/2005/11/18/493482.aspx

re: Regular Expressions From Scratch, Part Three: Concatenation

sebmol — Sat, 26 Nov 2005 03:53:53 GMT

I've been reading your posts but am wondering if you actually explained what the Kleene Closure is?

re: Regular Expressions From Scratch, Part Three: Concatenation

Derek — Sat, 26 Nov 2005 02:58:50 GMT

I noticed that no one had commented on the last RegEx post, or this one, and felt that I should speak up so you know at least one person is reading.

I'm interested in seeing more of this, and I'm sure plenty of others are, too. I like seeing experienced developers put together in-depth articles/tutorials/whatever-you-want-to-call-them.