Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Orderhttp://blogs.msdn.com/b/ericlippert/archive/2005/12/08/regular-expressions-from-scratch-part-seven-listing-all-members-of-a-language-in-order.aspxRegular languages are by definition those languages which can be described by a regular expression.
It should be clear from the definition that the union of any finite number of regular languages is a
regular language, the concatenation of any finiteen-USTelligent Evolution Platform Developer Build (Build: 5.6.50428.7875)Regular Expression: The Theory behind it!http://blogs.msdn.com/b/ericlippert/archive/2005/12/08/regular-expressions-from-scratch-part-seven-listing-all-members-of-a-language-in-order.aspx#543294Sat, 04 Mar 2006 02:29:40 GMT91d46819-8472-40ad-a661-2c78acb4018c:543294Dan Sellers's WebLogWhen it comes to validating input regular expression becomes a very important part of your security plan.&amp;nbsp;...<img src="http://blogs.msdn.com/aggbug.aspx?PostID=543294" width="1" height="1">Synesthesia » Links Roundup for 2006-02-21http://blogs.msdn.com/b/ericlippert/archive/2005/12/08/regular-expressions-from-scratch-part-seven-listing-all-members-of-a-language-in-order.aspx#536727Wed, 22 Feb 2006 12:18:23 GMT91d46819-8472-40ad-a661-2c78acb4018c:536727Synesthesia ยป Links Roundup for 2006-02-21PingBack from <a rel="nofollow" target="_new" href="http://www.synesthesia.co.uk/blog/archives/2006/02/22/links-24/">http://www.synesthesia.co.uk/blog/archives/2006/02/22/links-24/</a><img src="http://blogs.msdn.com/aggbug.aspx?PostID=536727" width="1" height="1">re: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Orderhttp://blogs.msdn.com/b/ericlippert/archive/2005/12/08/regular-expressions-from-scratch-part-seven-listing-all-members-of-a-language-in-order.aspx#502859Mon, 12 Dec 2005 23:48:54 GMT91d46819-8472-40ad-a661-2c78acb4018c:502859pndmnmpcooper, 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).
<br>
<br>(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...)
<br>
<br>Great sequence, I look forward to reading the rest of it.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=502859" width="1" height="1">re: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Orderhttp://blogs.msdn.com/b/ericlippert/archive/2005/12/08/regular-expressions-from-scratch-part-seven-listing-all-members-of-a-language-in-order.aspx#501744Fri, 09 Dec 2005 00:25:38 GMT91d46819-8472-40ad-a661-2c78acb4018c:501744Eric LippertYou two are using two different definitions of "order".
<br>
<br>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.
<br>
<br>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.
<br>
<br>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.
<br>
<br>Indeed, the set of real pairs is not enumerable. The set of reals is not enumerable either. The set of rationals is though.
<br><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=501744" width="1" height="1">re: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Orderhttp://blogs.msdn.com/b/ericlippert/archive/2005/12/08/regular-expressions-from-scratch-part-seven-listing-all-members-of-a-language-in-order.aspx#501736Fri, 09 Dec 2005 00:03:05 GMT91d46819-8472-40ad-a661-2c78acb4018c:501736pcooperOrdering 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).<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=501736" width="1" height="1">re: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Orderhttp://blogs.msdn.com/b/ericlippert/archive/2005/12/08/regular-expressions-from-scratch-part-seven-listing-all-members-of-a-language-in-order.aspx#501728Thu, 08 Dec 2005 23:44:07 GMT91d46819-8472-40ad-a661-2c78acb4018c:501728Lance FisherEvin, can you enumerate an infinite set? My intuative definition of enumerate is "make a (finite) list." Perhaps this is wrong.
<br>
<br>However, I do know that you can't order any old infinite set. Try ordering the points on a plane.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=501728" width="1" height="1">re: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Orderhttp://blogs.msdn.com/b/ericlippert/archive/2005/12/08/regular-expressions-from-scratch-part-seven-listing-all-members-of-a-language-in-order.aspx#501684Thu, 08 Dec 2005 22:32:36 GMT91d46819-8472-40ad-a661-2c78acb4018c:501684Eric LippertNo, "(a)" is not in R. Remember, the rule is:
<br>
<br>* if u and w are strings in R then (uw) is a string in R.
<br>
<br>"a" is a string in R, but the empty string is not, so (a) is not a string in R.
<br><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=501684" width="1" height="1">re: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Orderhttp://blogs.msdn.com/b/ericlippert/archive/2005/12/08/regular-expressions-from-scratch-part-seven-listing-all-members-of-a-language-in-order.aspx#501681Thu, 08 Dec 2005 22:27:48 GMT91d46819-8472-40ad-a661-2c78acb4018c:501681Jonas GrumbyI don't mean to join the pedantry dogpile, but did you skip (a) in your enumeration? (it's in R, right?)<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=501681" width="1" height="1">re: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Orderhttp://blogs.msdn.com/b/ericlippert/archive/2005/12/08/regular-expressions-from-scratch-part-seven-listing-all-members-of-a-language-in-order.aspx#501675Thu, 08 Dec 2005 22:18:24 GMT91d46819-8472-40ad-a661-2c78acb4018c:501675Eric LippertVery clever, and you are correct, the "clearly" is a big old hand-wave. :)
<br>
<br><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=501675" width="1" height="1">Enumerating Hhttp://blogs.msdn.com/b/ericlippert/archive/2005/12/08/regular-expressions-from-scratch-part-seven-listing-all-members-of-a-language-in-order.aspx#501672Thu, 08 Dec 2005 22:11:15 GMT91d46819-8472-40ad-a661-2c78acb4018c:501672EvinI'm not sure if the _you_ was a reference to my limited lifetime,
<br>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.
<br>
<br>If I could enumerate H ordered by length or alphabetically, I could solve H by calculating the appropriate number of elements in my list.
<br>
<br>If we're talking about languages in general, and not just the decidable ones, you must be careful with what can be done "clearly."<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=501672" width="1" height="1">re: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Orderhttp://blogs.msdn.com/b/ericlippert/archive/2005/12/08/regular-expressions-from-scratch-part-seven-listing-all-members-of-a-language-in-order.aspx#501656Thu, 08 Dec 2005 21:28:46 GMT91d46819-8472-40ad-a661-2c78acb4018c:501656Eric LippertEvin, I would argue that _you_ can't enumerate H because such an enumeration would require you to prove or disprove Goldbach's conjecture, amongst other things.
<br>
<br>My coming argument doesn't depend upon the fact that we can make an _alphabetical_ enumeration, just that we can make an enumeration which guarantees that every member of the set is on the enumeration somewhere. A length-then-alpha enumeration just happens to obviously have the property that it hits all of them and misses none of them. But any complete enumeration will do.
<br>
<br><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=501656" width="1" height="1">re: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Orderhttp://blogs.msdn.com/b/ericlippert/archive/2005/12/08/regular-expressions-from-scratch-part-seven-listing-all-members-of-a-language-in-order.aspx#501655Thu, 08 Dec 2005 21:23:17 GMT91d46819-8472-40ad-a661-2c78acb4018c:501655Eric LippertCorrect -- since an alphabet is by definition a finite set, then we can impose any total order relation we choose upon it. We could choose to define an alphabet as a sequence I suppose.
<br><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=501655" width="1" height="1">re: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Orderhttp://blogs.msdn.com/b/ericlippert/archive/2005/12/08/regular-expressions-from-scratch-part-seven-listing-all-members-of-a-language-in-order.aspx#501611Thu, 08 Dec 2005 20:05:44 GMT91d46819-8472-40ad-a661-2c78acb4018c:501611Lance FisherReinder, I believe the confusion here is the double use of the word alphabet which I'm sure you already understand. When Eric is talking about alphabetic order it's the normal English alphabetic order, but when he says S = {a,b} he's defining a Definition 1 type of alphabet.
<br>
<br>Certainly you can order any finite set, you just have to define the ordering, just like he did with R.
<br>
<br>Is there any reason why we can't define an alphabet as an ordered set?<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=501611" width="1" height="1">Clearly given any language that we can enumerate at all...http://blogs.msdn.com/b/ericlippert/archive/2005/12/08/regular-expressions-from-scratch-part-seven-listing-all-members-of-a-language-in-order.aspx#501589Thu, 08 Dec 2005 19:12:36 GMT91d46819-8472-40ad-a661-2c78acb4018c:501589EvinLet H be the language containing all pairs of programs and inputs for which the program halts with the given input.
<br>
<br>I can enumerate H. But I cannot enumerate H ordered first by length and then alphabetically.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=501589" width="1" height="1">re: Regular Expressions From Scratch, Part Seven: Listing All Members Of A Language In Orderhttp://blogs.msdn.com/b/ericlippert/archive/2005/12/08/regular-expressions-from-scratch-part-seven-listing-all-members-of-a-language-in-order.aspx#501587Thu, 08 Dec 2005 19:08:09 GMT91d46819-8472-40ad-a661-2c78acb4018c:501587Reinder Verlinde<pedantic>
<br>"Consider an alphabet, say S = {a, b}. We can enumerate all the strings of S* first by length and then by alphabetical order"
<br>
<br>No, we can't. In <<a rel="nofollow" target="_new" href="http://blogs.msdn.com/ericlippert/archive/2005/11/18/493482.aspx>">http://blogs.msdn.com/ericlippert/archive/2005/11/18/493482.aspx></a>, you said "Definition 1: An alphabet is a finite set of symbols".
<br>
<br>A set does not have an order. Because of this, you can sort on length, but not on alphabet.
<br>
<br>The mathematician in me saw this logical error coming in part 1 (to be honest, I expected it to become problematic when you started mentioning things like [a-z]).
<br></pedantic>
<br><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=501587" width="1" height="1">