Browse by Tags

• Rarefied Heights

• Regular Expressions From Scratch, Part Twelve: Superposition of States

  Happy New Year everyone. Over the break I had a wonderful time reconnecting with my friends and family. And of course I came back to a huge pile of work! We're going through the flaws that were discovered in C# 2.0 too late in the cycle to risk fixing, Read More... Posted Friday, January 20, 2006 11:47 AM by Eric Lippert | 6 Comments Filed under: Rarefied Heights, Regular Expressions

• Regular Expressions From Scratch, Part Eleven: Eliminating Multi-Symbol Rules

  The story so far: we have deterministic and nondeterministic finite automata. DFAs follow a rigid, fully specified set of rules which, on any string, yield either an accept or reject state after exactly as many moves as the string has characters. NFAs, Read More... Posted Thursday, December 22, 2005 7:00 AM by Eric Lippert | 3 Comments Filed under: Rarefied Heights, Regular Expressions

• Regular Expressions From Scratch, Part Ten: Magic!

  Let's recap the story so far. Starting only with basic set theory, sequences, symbols and numbers, we've defined alphabets, languages, regular expressions, and the mapping between regular expressions and regular languages. We've also defined deterministic Read More... Posted Monday, December 19, 2005 7:00 AM by Eric Lippert | 2 Comments Filed under: Rarefied Heights, Regular Expressions

• Regular Expressions From Scratch, Part Nine: A Dream of a Machine

  I want to come up with the simplest possible device that can identify whether a given string is a member of a given regular language. We need some kind of computer, but to make it easy to analyze, I want to put as many restrictions upon it as possible. Read More... Posted Thursday, December 15, 2005 7:28 AM by Eric Lippert | 8 Comments Filed under: Rarefied Heights, Regular Expressions

• Regular Expressions From Scratch, Part Eight: The Diagonal Argument

  As we know, each regular expression is associated with a language by our function L. We also determined last time that we could list all members of S* and R in order first by length and then by alphabetical order. Here's a weird question: is the nth string Read More... Posted Monday, December 12, 2005 7:00 AM by Eric Lippert | 2 Comments Filed under: Rarefied Heights, Regular Expressions

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

  Regular 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 finite Read More... Posted Thursday, December 08, 2005 7:00 AM by Eric Lippert | 15 Comments Filed under: Rarefied Heights, Regular Expressions

• Regular Expressions From Scratch, Part Six: The Insanely Clever Bit

  Let's start with an easy one today, because things are about to get a little tricky. Definition 10 : a pair is a finite sequence with exactly two members. Definition 11 : a function is a set of pairs, where the second member of each pair is the value Read More... Posted Monday, December 05, 2005 7:10 AM by Eric Lippert | 5 Comments Filed under: Rarefied Heights, Regular Expressions

• Regular Expressions From Scratch, Part Five: The Regular Expression Language

  Now things start to get really weird. Definition 9 : Take any alphabet S. The regular expression alphabet of S is S plus a bunch of extra symbols; it's S ∪ { ( , ) , * , ∪ , Ø } (I assume that none of those symbols are already in Read More... Posted Thursday, December 01, 2005 7:00 AM by Eric Lippert | 10 Comments Filed under: Rarefied Heights, Regular Expressions

• Regular Expressions From Scratch, Part Four: The Kleene Closure of a Language

  Languages are sets, so we can take any two languages (over the same alphabet) and take their union to form a new language. Just as a reminder: Definition 7 : The union of two sets L and K is the set with all the members found in either , and is written Read More... Posted Monday, November 28, 2005 7:00 AM by Eric Lippert | 6 Comments Filed under: Rarefied Heights, Regular Expressions

• Regular Expressions From Scratch, Part Three: Concatenation

  You probably intuitively understood concatenation already, but let me define it anyway. Definition 5 : The concatenation of two strings w and u (over the same alphabet) makes a string consisting of the sequence of every element in w followed by every Read More... Posted Friday, November 25, 2005 7:00 AM by Eric Lippert | 9 Comments Filed under: Rarefied Heights, Regular Expressions

• Regular Expressions From Scratch, Part Two: Some Examples of Languages

  Let's look at some sample languages to get a sense of just how flexible languages can be. For example, here are some languages over the alphabet S = { 0 , 1 } L 1 = all members of S*, period -- the language where every string is in the language L 2 = Read More... Posted Tuesday, November 22, 2005 7:00 AM by Eric Lippert | 2 Comments Filed under: Rarefied Heights, Regular Expressions

• Regular Expressions From Scratch, Part One: Defining Terms

  Over the years that I've been writing this blog some of the most positive feedback I've received has been for those entries where I've explored fundamental concepts in computer science. I thought that I might take that to its logical extreme, and do a Read More... Posted Friday, November 18, 2005 10:00 AM by Eric Lippert | 18 Comments Filed under: Rarefied Heights, Regular Expressions