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. They somehow magically are able to…


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 strings one character at a time, change their internal state to one of…


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…


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…


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, and the Kleene Closure of any…


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 by the function….


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 that I said earlier that I…


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…


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 the same way as before: all run together….


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} L1 = all members of S*, period — the language where every string is in the language L2 = all members of S* such that…