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 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….