Browse by Tags

Tagged Content List
  • Blog Post: Back in the saddle

    Hey everyone, I'm back. Sorry for the two-month absence there. We've been absolutely INSANELY busy trying to figure out how to make the LINQ features work in C# 3.0 for the last two months. Add on top of that the fact that I've been running lights for an amateur theatre production for the last couple...
  • Blog Post: 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, and some of them illustrate interesting corner...
  • Blog Post: 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, on the other hand, are poorly specified. ...
  • Blog Post: 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 finite automata as machines that take in...
  • Blog Post: 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. For example, I want there to be very limited...
  • Blog Post: 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 in S*'s alphabetical ordering a member of...
  • Blog Post: 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 number of regular languages is a regular language...
  • Blog Post: 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 associated with the first member...
  • Blog Post: 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 S.) I'm doing something...
  • Blog Post: 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 L ∪ K. We're going to take...
  • Blog Post: 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 element in u. We write concatenations...
  • Blog Post: 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 = all members of S* such that...
  • Blog Post: 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 series on what exactly a "regular expression...
Page 1 of 1 (13 items)