Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Order

Regular Expression: The Theory behind it!

Dan Sellers's WebLog — Sat, 04 Mar 2006 02:29:40 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:23 GMT

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

re: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Order

pndmnm — Mon, 12 Dec 2005 23:48:54 GMT

pcooper, it's worth noting that a total order on the pairs of reals isn't nearly as useful as giving them field order would be (a field is "ordered" if you can seperate the non-zero elements into two sets, P and N, x is in P if and only if -x is in N, and P is closed under the field operations) -- the standard field of pairs of reals (the complex plane) cannot be ordered in this fashion (by Artin-Schreier).

(I realize this has little to nothing to do with the topic at hand, but if anyone gets here by googling for orders on pairs of reals...)

Great sequence, I look forward to reading the rest of it.

re: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Order

Eric Lippert — Fri, 09 Dec 2005 00:25:38 GMT

You two are using two different definitions of "order".

pcooper is describing a total order on an arbitrary set. That is, given any two members of the set can we consistently describe whether one is >, = or < the other. Total orders should have nice properties like antisymmetry and transitivity.

Lance is describing enumeration. An enumeration imposes a total order on a set, but there are sets that can be ordered that cannot be enumerated.

By "enumerated" I mean "put into 1-1 correspondance with the positive integers". That is, for every positive integer you can find a unique associated member, and for every member you can find a unique integer.

Indeed, the set of real pairs is not enumerable. The set of reals is not enumerable either. The set of rationals is though.

re: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Order

pcooper — Fri, 09 Dec 2005 00:03:05 GMT

Ordering the points on a plane doesn't seem all that hard. Point (x1,y1) < Point (x2,y2) if (x1 < x2) or (x1 = x2 and y1 < y2).

re: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Order

Lance Fisher — Thu, 08 Dec 2005 23:44:07 GMT

Evin, can you enumerate an infinite set? My intuative definition of enumerate is "make a (finite) list." Perhaps this is wrong.

However, I do know that you can't order any old infinite set. Try ordering the points on a plane.

re: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Order

Eric Lippert — Thu, 08 Dec 2005 22:32:36 GMT

No, "(a)" is not in R. Remember, the rule is:

* if u and w are strings in R then (uw) is a string in R.

"a" is a string in R, but the empty string is not, so (a) is not a string in R.

re: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Order

Jonas Grumby — Thu, 08 Dec 2005 22:27:48 GMT

I don't mean to join the pedantry dogpile, but did you skip (a) in your enumeration? (it's in R, right?)

re: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Order

Eric Lippert — Thu, 08 Dec 2005 22:18:24 GMT

Very clever, and you are correct, the "clearly" is a big old hand-wave. :)

Enumerating H

Evin — Thu, 08 Dec 2005 22:11:15 GMT

I'm not sure if the _you_ was a reference to my limited lifetime,
but I can enumerate H as well as I can enumerate any other infinite set. The order of my enumeration is very important. First I will list all programs and inputs of length 1 which halt in 1 operation. Then I will list those no longer than 2 which halt in 2 or fewer operations (skipping those that I listed before). And so on. I will eventually list every member of H (and each will be in a well-defined position). I probably wouldn't get around to Goldbach's conjecture before the Sun expands, but if it is false, I would eventually list a program searching for the even number which disproves it.

If I could enumerate H ordered by length or alphabetically, I could solve H by calculating the appropriate number of elements in my list.

If we're talking about languages in general, and not just the decidable ones, you must be careful with what can be done "clearly."