A finite automaton has no permanent storage and virtually no RAM. It’s a little machine with a handful of possible states and the ability to keep track of which one of those states it’s currently in—think of it as a computer with enough RAM to store a single value. Similarly, finite automata don’t have a keyboard, mouse, or network interface for receiving input, just a single external stream of input characters that they can read one at a time.

Instead of a general-purpose CPU for executing arbitrary programs, each finite automaton has a hardcoded collection of rules that determine how it should move from one state to another in response to input. The automaton starts in one particular state and reads individual characters from its input stream, following a rule each time it reads a character.

Here’s a way of visualizing the structure of one particular finite automaton:

The two circles represent the automaton’s two states, 1 and 2, and the arrow coming from nowhere shows that the automaton always starts in state 1, its start state. The arrows between states represent the rules of the machine, which are:

This is enough information for us to investigate how the machine processes a stream of inputs:

Once it gets back to state 1, it’ll start repeating itself, so that’s the extent of this particular machine’s behavior. Information about the current state is assumed to be internal to the automaton—it operates as a “black box” that doesn’t reveal its inner workings—so the boringness of this behavior is compounded by the uselessness of it not causing any kind of observable output. Nobody in the outside world can see that anything is happening while the machine is bouncing between states 1 and 2, so in this case, we might as well have a single state and not bother with any internal structure at all.

To address this problem, finite automata also have a rudimentary way of producing output. This is nothing as sophisticated as the output capabilities of real computers; we just mark some of the states as being special, and say that the machine’s single-bit output is the information about whether it’s currently in a special state or not. For this machine, let’s make state 2 a special state and show it on the diagram with a double circle:

These special states are usually called accept states, which suggests the idea of a machine accepting or rejecting certain sequences of inputs. If this automaton starts in state 1 and reads a single a, it will be left in state 2, which is an accept state, so we can say that the machine accepts the string 'a'. On the other hand, if it first reads an a and then another a, it’ll end up back in state 1, which isn’t an accept state, so the machine rejects the string 'aa'. In fact, it’s easy to see that this machine accepts any string of as whose length is an odd number: 'a', 'aaa', 'aaaaa' are all accepted, while 'aa', 'aaaa', and '' (the empty string) are rejected.

Now we have something slightly more useful: a machine that can read a sequence of characters and provide a yes/no output to indicate whether that sequence has been accepted. It’s reasonable to say that this DFA is performing a computation, because we can ask it a question—“is the length of this string an odd number?”—and get a meaningful reply back. This is arguably enough to call it a simple computer, and we can see how its features stack up against a real computer:

Of course, this specific automaton doesn’t do anything sophisticated or useful, but we can build more complex automata that have more states and can read more than one character. Here’s one with three states and the ability to read the inputs a and b:

This machine accepts strings like 'ab', 'baba', and 'aaaab', and rejects strings like 'a', 'baa', and 'bbbba'. A bit of experimentation shows that it will only accept strings that contain the sequence 'ab', which still isn’t hugely useful but at least demonstrates a degree of subtlety. We’ll see more practical applications later in the chapter.

Significantly, this kind of automaton is deterministic: whatever state it’s currently in, and whichever character it reads, it’s always absolutely certain which state it will end up in. This certainty is guaranteed as long as we respect two constraints:

Taken together, these constraints mean that the machine must have exactly one rule for each combination of state and input. The technical name for a machine that obeys the determinism constraints is a deterministic finite automaton (DFA).

Deterministic finite automata are intended as abstract models of computation. We’ve drawn diagrams of a couple of example machines and thought about their behavior, but these machines don’t physically exist, so we can’t literally feed them input and see how they behave. Fortunately DFAs are so simple that we can easily build a simulation of one in Ruby and interact with it directly.

Let’s begin building that simulation by implementing a collection of rules, which we’ll call a rulebook:

class FARule < Struct.new(:state, :character, :next_state)
  def applies_to?(state, character)
    self.state == state && self.character == character
  end

  def follow
    next_state
  end

  def inspect
    "#<FARule #{state.inspect} --#{character}--> #{next_state.inspect}>"
  end
end

class DFARulebook < Struct.new(:rules)
  def next_state(state, character)
    rule_for(state, character).follow
  end

  def rule_for(state, character)
    rules.detect { |rule| rule.applies_to?(state, character) }
  end
end

This code establishes a simple API for rules: each rule has an #applies_to? method, which returns true or false to indicate whether that rule applies in a particular situation, and a #follow method that returns information about how the machine should change when a rule is followed.^[20] DFARulebook#next_state uses these methods to locate the correct rule and discover what the next state of the DFA should be.

A rulebook lets us wrap up many rules into a single object and ask it questions about which state comes next:

>> rulebook = DFARulebook.new([
     FARule.new(1, 'a', 2), FARule.new(1, 'b', 1),
     FARule.new(2, 'a', 2), FARule.new(2, 'b', 3),
     FARule.new(3, 'a', 3), FARule.new(3, 'b', 3)
   ])
=> #<struct DFARulebook …>
>> rulebook.next_state(1, 'a')
=> 2
>> rulebook.next_state(1, 'b')
=> 1
>> rulebook.next_state(2, 'b')
=> 3

Once we have a rulebook, we can use it to build a DFA object that keeps track of its current state and can report whether it’s currently in an accept state or not:

class DFA < Struct.new(:current_state, :accept_states, :rulebook)
  def accepting?
    accept_states.include?(current_state)
  end
end

>> DFA.new(1, [1, 3], rulebook).accepting?
=> true
>> DFA.new(1, [3], rulebook).accepting?
=> false

We can now write a method to read a character of input, consult the rulebook, and change state accordingly:

class DFA
  def read_character(character)
    self.current_state = rulebook.next_state(current_state, character)
  end
end

This lets us feed characters to the DFA and watch its output change:

>> dfa = DFA.new(1, [3], rulebook); dfa.accepting?
=> false
>> dfa.read_character('b'); dfa.accepting?
=> false
>> 3.times do dfa.read_character('a') end; dfa.accepting?
=> false
>> dfa.read_character('b'); dfa.accepting?
=> true

Feeding the DFA one character at a time is a little unwieldy, so let’s add a convenience method for reading an entire string of input:

class DFA
  def read_string(string)
    string.chars.each do |character|
      read_character(character)
    end
  end
end

Now we can provide the DFA a whole string of input instead of having to pass its characters individually:

>> dfa = DFA.new(1, [3], rulebook); dfa.accepting?
=> false
>> dfa.read_string('baaab'); dfa.accepting?
=> true

Once a DFA object has been fed some input, it’s probably not in its start state anymore, so we can’t reliably reuse it to check a completely new sequence of inputs. That means we have to recreate it from scratch—using the same start state, accept states, and rulebook as before—every time we want to see whether it will accept a new string. We can avoid doing this manually by wrapping up its constructor’s arguments in an object that represents the design of a particular DFA and relying on that object to automatically build one-off instances of that DFA whenever we want to check for acceptance of a string:

class DFADesign < Struct.new(:start_state, :accept_states, :rulebook)
  def to_dfa
    DFA.new(start_state, accept_states, rulebook)
  end

  def accepts?(string)
    to_dfa.tap { |dfa| dfa.read_string(string) }.accepting?
  end
end

DFADesign#accepts? uses the DFADesign#to_dfa method to create a new instance of DFA and then calls #read_string? to put it into an accepting or rejecting state:

>> dfa_design = DFADesign.new(1, [3], rulebook)
=> #<struct DFADesign …>
>> dfa_design.accepts?('a')
=> false
>> dfa_design.accepts?('baa')
=> false
>> dfa_design.accepts?('baba')
=> true

Suppose we wanted a finite automaton that would accept any string of as and bs as long as the third character was b. It’s easy enough to come up with a suitable DFA design:

What if we wanted a machine that would accept strings where the third-from-last character is b? How would that work? It seems more difficult: the DFA above is guaranteed to be in state 3 when it reads the third character, but a machine can’t know in advance when it’s reading the third-from-last character, because it doesn’t know how long the string is until it’s finished reading it. It might not be immediately clear whether such a DFA is even possible.

However, if we relax the determinism constraints and allow the rulebook to contain multiple rules (or no rules at all) for a given state and input, we can design a machine that does the job:

This state machine, a nondeterministic finite automaton (NFA), no longer has exactly one execution path for each sequence of inputs. When it’s in state 1 and reads b as input, it’s possible for it to follow a rule that keeps it in state 1, but it’s also possible for it to follow a different rule that takes it into state 2 instead. Conversely, once it gets into state 4, it has no rules to follow and therefore no way to read any more input. A DFA’s next state is always completely determined by its current state and its input, but an NFA sometimes has more than one possibility for which state to move into next, and sometimes none at all.

A DFA accepts a string if reading the characters and blindly following the rules causes the machine to end up in an accept state, so what does it mean for an NFA to accept or reject a string? The natural answer is that a string is accepted if there’s some way for the NFA to end up in an accept state by following some of its rules—that is, if finishing in an accept state is possible, even if it’s not inevitable.

For example, this NFA accepts the string 'baa', because, starting at state 1, the rules say there is a way for the machine to read a b and move into state 2, then read an a and move into state 3, and finally read another a and finish in state 4, which is an accept state. It also accepts the string 'bbbbb', because it’s possible for the NFA to initially follow a different rule and stay in state 1 while reading the first two bs, and only use the rule for moving into state 2 when reading the third b, which then lets it read the rest of the string and finish in state 4 as before.

On the other hand, there’s no way for it to read 'abb' and end up in state 4—depending on which rules it follows, it can only end up in state 1, 2, or 3—so 'abb' is not accepted by this NFA. Neither is 'bbabb', which can only ever get as far as state 3; if it goes straight into state 2 when reading the first b, it will end up in state 4 too early, with two characters still left to read but no more rules to follow.

Relaxing the determinism constraints has produced an imaginary machine that is very different from the real, deterministic computers we’re familiar with. An NFA deals in possibilities rather than certainties; we talk about its behavior in terms of what can happen rather than what will happen. This seems powerful, but how can such a machine work in the real world? At first glance it looks like a real implementation of an NFA would need some kind of foresight in order to know which of several possibilities to choose while it reads input: to stand a chance of accepting a string, our example NFA must stay in state 1 until it reads the third-from-last character, but it has no way of knowing how many more characters it will receive. How can we simulate an exciting machine like this in boring, deterministic Ruby?

The key to simulating an NFA on a deterministic computer is to find a way to explore all possible executions of the machine. This brute-force approach eliminates the spooky foresight that would be required to simulate only one possible execution by somehow making all the right decisions along the way. When an NFA reads a character, there are only ever a finite number of possibilities for what it can do next, so we can simulate the nondeterminism by somehow trying all of them and seeing whether any of them ultimately allows it to reach an accept state.

We could do this by recursively trying all possibilities: each time the simulated NFA reads a character and there’s more than one applicable rule, follow one of those rules and try reading the rest of the input; if that doesn’t leave the machine in an accept state, then go back into the earlier state, rewind the input to its earlier position, and try again by following a different rule; repeat until some choice of rules leads to an accept state, or until all possible choices have been tried without success.

Another strategy is to simulate all possibilities in parallel by spawning new threads every time the machine has more than one rule it can follow next, effectively copying the simulated NFA so that each copy can try a different rule to see how it pans out. All those threads can be run at once, each reading from its own copy of the input string, and if any thread ends up with a machine that’s read every character and stopped in an accept state, then we can say the string has been accepted.

Both of these implementations are feasible, but they’re a bit complicated and inefficient. Our DFA simulation was simple and could read individual characters while constantly reporting back on whether the machine is in an accept state, so it would be nice to simulate an NFA in a way that gives us the same simplicity and transparency.

Fortunately, there’s an easy way to simulate an NFA without needing to rewind our progress, spawn threads, or know all the input characters in advance. In fact, just as we simulated a single DFA by keeping track of its current state, we can simulate a single NFA by keeping track of all its possible current states. This is simpler and more efficient than simulating multiple NFAs that go off in different directions, and it turns out to achieve the same thing in the end. If we did simulate many separate machines, then all we’d care about is what state each of them was in, but any machines in the same state are completely indistinguishable,^[21] so we don’t lose anything by collapsing all those possibilities down into a single machine and asking “which states could it be in by now?” instead.

For example, let’s walk through what happens to our example NFA as it reads the string 'bab':

This simulation strategy is easy to turn into code. First we need a rulebook suitable for storing an NFA’s rules. A DFA rulebook always returns a single state when we ask it where the DFA should go next after reading a particular character while in a specific state, but an NFA rulebook needs to answer a different question: when an NFA is possibly in one of several states, and it reads a particular character, what states can it possibly be in next? The implementation looks like this:

require 'set'

class NFARulebook < Struct.new(:rules)
  def next_states(states, character)
    states.flat_map { |state| follow_rules_for(state, character) }.to_set
  end

  def follow_rules_for(state, character)
    rules_for(state, character).map(&:follow)
  end

  def rules_for(state, character)
    rules.select { |rule| rule.applies_to?(state, character) }
  end
end

We can create a nondeterministic rulebook and ask it questions:

>> rulebook = NFARulebook.new([
     FARule.new(1, 'a', 1), FARule.new(1, 'b', 1), FARule.new(1, 'b', 2),
     FARule.new(2, 'a', 3), FARule.new(2, 'b', 3),
     FARule.new(3, 'a', 4), FARule.new(3, 'b', 4)
   ])
=> #<struct NFARulebook rules=[…]>
>> rulebook.next_states(Set[1], 'b')
=> #<Set: {1, 2}>
>> rulebook.next_states(Set[1, 2], 'a')
=> #<Set: {1, 3}>
>> rulebook.next_states(Set[1, 3], 'b')
=> #<Set: {1, 2, 4}>

The next step is to implement an NFA class to represent the simulated machine:

class NFA < Struct.new(:current_states, :accept_states, :rulebook)
  def accepting?
    (current_states & accept_states).any?
  end
end

This NFA class is very similar to our DFA class from earlier. The difference is that it has a set of possible current_states instead of a single definite current_state, so it’ll say it’s in an accept state if any of its current_states is an accept state:

>> NFA.new(Set[1], [4], rulebook).accepting?
=> false
>> NFA.new(Set[1, 2, 4], [4], rulebook).accepting?
=> true

As with the DFA class, we can implement a #read_character method for reading a single character of input, and a #read_string method for reading several in sequence:

class NFA
  def read_character(character)
    self.current_states = rulebook.next_states(current_states, character)
  end

  def read_string(string)
    string.chars.each do |character|
      read_character(character)
    end
  end
end

These methods really are almost identical to their DFA counterparts; we’re just saying current_states and next_states in #read_character instead of current_state and next_state.

That’s the hard work over with. Now we’re able to start a simulated NFA, pass characters in, and ask whether the input so far has been accepted:

>> nfa = NFA.new(Set[1], [4], rulebook); nfa.accepting?
=> false
>> nfa.read_character('b'); nfa.accepting?
=> false
>> nfa.read_character('a'); nfa.accepting?
=> false
>> nfa.read_character('b'); nfa.accepting?
=> true
>> nfa = NFA.new(Set[1], [4], rulebook)
=> #<struct NFA current_states=#<Set: {1}>, accept_states=[4], rulebook=…>
>> nfa.accepting?
=> false
>> nfa.read_string('bbbbb'); nfa.accepting?
=> true

As we saw with the DFA class, it’s convenient to use an NFADesign object to automatically manufacture new NFA instances on demand rather than creating them manually:

class NFADesign < Struct.new(:start_state, :accept_states, :rulebook)
  def accepts?(string)
    to_nfa.tap { |nfa| nfa.read_string(string) }.accepting?
  end

  def to_nfa
    NFA.new(Set[start_state], accept_states, rulebook)
  end
end

This makes it easier to check different strings against the same NFA:

>> nfa_design = NFADesign.new(1, [4], rulebook)
=> #<struct NFADesign start_state=1, accept_states=[4], rulebook=…>
>> nfa_design.accepts?('bab')
=> true
>> nfa_design.accepts?('bbbbb')
=> true
>> nfa_design.accepts?('bbabb')
=> false

And that’s it: we’ve successfully built a simple implementation of an unusual nondeterministic machine by simulating all of its possible executions. Nondeterminism is a convenient tool for designing more sophisticated finite automata, so it’s fortunate that NFAs are usable in practice rather than just a theoretical curiosity.

We’ve seen how relaxing the determinism constraints gives us new ways of designing machines without sacrificing our ability to implement them. What else can we safely relax to give ourselves more design freedom?

It’s easy to design a DFA that accepts strings of as whose length is a multiple of two ('aa', 'aaaa'…):

But how can we design a machine that accepts strings whose length is a multiple of two or three? We know that nondeterminism gives a machine more than one execution path to follow, so perhaps we can design an NFA that has one “multiple of two” path and one “multiple of three” path. A naïve attempt might look like this:

The idea here is for the NFA to move between states 1 and 2 to accept strings like 'aa' and 'aaaa', and between states 1, 3, and 4 to accept strings like 'aaa' and 'aaaaaaaaa'. That works fine, but the problem is that the machine also accepts the string 'aaaaa', because it can move from state 1 to state 2 and back to 1 when reading the first two characters, and then move through states 3, 4, and back to 1 when reading the next three, ending up in an accept state even though the string’s length is not a multiple of two or three.^[22]

Again it may not be immediately obvious whether an NFA can do this job at all, but we can address the problem by introducing another machine feature called free moves. These are rules that the machine may spontaneously follow without reading any input, and they help here because they give the NFA an initial choice between two separate groups of states:

The free moves are shown by the dotted unlabeled arrows from state 1 to states 2 and 4. This machine can still accept the string 'aaaa' by spontaneously moving into state 2, and then moving between states 2 and 3 as it reads the input, and likewise for 'aaaaaaaaa' if it begins with a free move into state 4. Now, though, there is no way for it to accept the string 'aaaaa': in any possible execution, it must begin by committing to a free move into either state 2 or state 4, and once it’s gone one way, there’s no route back again. Once it’s in state 2, it can only accept a string whose length is a multiple of 2, and likewise once it’s in state 4, it can only accept a string whose length is a multiple of 3.

How do we support free moves in our Ruby NFA simulation? Well, this new choice between staying in state 1, spontaneously moving into state 2, or spontaneously moving into state 4 is not really any stranger than the nondeterminism we already have, and our implementation can handle it in a similar way. We already have the idea of a simulated machine having many possible states at once, so we just need to broaden those possible states to include any that are reachable by performing one or more free moves. In this case, the machine starting in state 1 really means that it can be in state 1, 2, or 4 before it’s read any input.

First we need a way to represent free moves in Ruby. The easiest way is to use normal FARule instances with a nil where a character should be. Our existing implementation of NFARulebook will treat nil like any other character, so we can ask “from state 1, what states can we get to by performing one free move?” (instead of “…by reading one a character?”):

>> rulebook = NFARulebook.new([
     FARule.new(1, nil, 2), FARule.new(1, nil, 4),
     FARule.new(2, 'a', 3),
     FARule.new(3, 'a', 2),
     FARule.new(4, 'a', 5),
     FARule.new(5, 'a', 6),
     FARule.new(6, 'a', 4)
   ])
=> #<struct NFARulebook rules=[…]>
>> rulebook.next_states(Set[1], nil)
=> #<Set: {2, 4}>

Next we need some helper code for finding all the states that can be reached by following free moves from a particular set of states. This code will have to follow free moves repeatedly, because an NFA can spontaneously change states as many times as it likes as long as there are free moves leading from its current state. A method on the NFARulebook class is a convenient place to put it:

class NFARulebook
  def follow_free_moves(states)
    more_states = next_states(states, nil)

    if more_states.subset?(states)
      states
    else
      follow_free_moves(states + more_states)
    end
  end
end

NFARulebook#follow_free_moves works by recursively looking for more and more states that can be reached from a given set of states by following free moves. When it can’t find any more—that is, when every state found by next_states(states, nil) is already in states—it returns all the states it’s found.^[23]

This code correctly identifies the possible states of our NFA before it’s read any input:

>> rulebook.follow_free_moves(Set[1])
=> #<Set: {1, 2, 4}>

Now we can bake this free move support into NFA by overriding the existing implementation of NFA#current_states (as provided by Struct). Our new implementation will hook into NFARulebook#follow_free_moves and ensure that the possible current states of the automaton always include any states that are reachable via free moves:

class NFA
  def current_states
    rulebook.follow_free_moves(super)
  end
end

Since all other NFA methods access the set of possible current states by calling the #current_states method, this transparently provides support for free moves without having to change the rest of NFA’s code.

That’s it. Now our simulation supports free moves, and we can see which strings are accepted by our NFA:

>> nfa_design = NFADesign.new(1, [2, 4], rulebook)
=> #<struct NFADesign …>
>> nfa_design.accepts?('aa')
=> true
>> nfa_design.accepts?('aaa')
=> true
>> nfa_design.accepts?('aaaaa')
=> false
>> nfa_design.accepts?('aaaaaa')
=> true

So free moves are pretty straightforward to implement, and they give us extra design freedom on top of what nondeterminism already provides.

Let’s be precise about what we mean by “regular expression.” To get us off the ground, here are two kinds of extremely simple regular expression that are not built out of anything simpler:

Once we have these simple kinds of pattern, there are three ways we can combine them to build more complex expressions:

To implement this syntax in Ruby, we can define a class for each kind of regular expression and use instances of those classes to represent the abstract syntax tree of any regular expression, just as we did for Simple expressions in Chapter 2:

module Pattern
  def bracket(outer_precedence)
    if precedence < outer_precedence
      '(' + to_s + ')'
    else
      to_s
    end
  end

  def inspect
    "/#{self}/"
  end
end

class Empty
  include Pattern

  def to_s
    ''
  end

  def precedence
    3
  end
end

class Literal < Struct.new(:character)
  include Pattern

  def to_s
    character
  end

  def precedence
    3
  end
end

class Concatenate < Struct.new(:first, :second)
  include Pattern

  def to_s
    [first, second].map { |pattern| pattern.bracket(precedence) }.join
  end

  def precedence
    1
  end
end

class Choose < Struct.new(:first, :second)
  include Pattern

  def to_s
    [first, second].map { |pattern| pattern.bracket(precedence) }.join('|')
  end

  def precedence
    0
  end
end

class Repeat < Struct.new(:pattern)
  include Pattern

  def to_s
    pattern.bracket(precedence) + '*'
  end

  def precedence
    2
  end
end

These classes let us manually build trees to represent regular expressions:

>> pattern =
     Repeat.new(
       Choose.new(
         Concatenate.new(Literal.new('a'), Literal.new('b')),
         Literal.new('a')
       )
     )
=> /(ab|a)*/

Of course, in a real implementation, we’d use a parser to build these trees instead of constructing them by hand; see Parsing for instructions on how to do this.

Now that we have a way of representing the syntax of a regular expression as a tree of Ruby objects, how can we convert that syntax into an NFA?

We need to decide how instances of each syntax class should be turned into NFAs. The easiest class to convert is Empty, which we should always turn into the one-state NFA that only accepts the empty string:

Similarly, we should turn any literal, single-character pattern into the NFA that only accepts the single-character string containing that character. Here’s the NFA for the pattern a:

It’s easy enough to implement #to_nfa_design methods for Empty and Literal to generate these NFAs:

class Empty
  def to_nfa_design
    start_state = Object.new
    accept_states = [start_state]
    rulebook = NFARulebook.new([])

    NFADesign.new(start_state, accept_states, rulebook)
  end
end

class Literal
  def to_nfa_design
    start_state = Object.new
    accept_state = Object.new
    rule = FARule.new(start_state, character, accept_state)
    rulebook = NFARulebook.new([rule])

    NFADesign.new(start_state, [accept_state], rulebook)
  end
end

We can check that the NFAs generated from Empty and Literal regular expressions accept the strings we want them to:

>> nfa_design = Empty.new.to_nfa_design
=> #<struct NFADesign …>
>> nfa_design.accepts?('')
=> true
>> nfa_design.accepts?('a')
=> false
>> nfa_design = Literal.new('a').to_nfa_design
=> #<struct NFADesign …>
>> nfa_design.accepts?('')
=> false
>> nfa_design.accepts?('a')
=> true
>> nfa_design.accepts?('b')
=> false

There’s an opportunity here to wrap #to_nfa_design in a #matches? method to give patterns a nicer interface:

module Pattern
  def matches?(string)
    to_nfa_design.accepts?(string)
  end
end

This lets us match patterns directly against strings:

>> Empty.new.matches?('a')
=> false
>> Literal.new('a').matches?('a')
=> true

Now that we know how to turn simple Empty and Literal regular expressions into NFAs, we need a similar setup for Concatenate, Choose, and Repeat.

Let’s begin with Concatenate: if we have two regular expressions that we already know how to turn into NFAs, how can we build an NFA to represent the concatenation of those regular expressions? For example, given that we can turn the single-character regular expressions a and b into NFAs, how do we turn ab into one?

In the ab case, we can connect the two NFAs in sequence, joining them together with a free move, and keeping the second NFA’s accept state:

This technique works in other cases too. Any two NFAs can be concatenated by turning every accept state from the first NFA into a nonaccept state and connecting it to the start state of the second NFA with a free move. Once the concatenated machine has read a sequence of inputs that would have put the first NFA into an accept state, it can spontaneously move into a state corresponding to the start state of the second NFA, and then reach an accept state by reading a sequence of inputs that the second NFA would have accepted.

So, the raw ingredients for the combined machine are:

We can turn this idea into an implementation of Concatenate#to_nfa_design:

class Concatenate
  def to_nfa_design
    first_nfa_design = first.to_nfa_design
    second_nfa_design = second.to_nfa_design

    start_state = first_nfa_design.start_state
    accept_states = second_nfa_design.accept_states
    rules = first_nfa_design.rulebook.rules + second_nfa_design.rulebook.rules
    extra_rules = first_nfa_design.accept_states.map { |state|
      FARule.new(state, nil, second_nfa_design.start_state)
    }
    rulebook = NFARulebook.new(rules + extra_rules)

    NFADesign.new(start_state, accept_states, rulebook)
  end
end

This code first converts the first and second regular expressions into NFADesigns, then combines their states and rules in the appropriate way to make a new NFADesign. It works as expected for the simple ab case:

>> pattern = Concatenate.new(Literal.new('a'), Literal.new('b'))
=> /ab/
>> pattern.matches?('a')
=> false
>> pattern.matches?('ab')
=> true
>> pattern.matches?('abc')
=> false

This conversion process is recursive—Concatenate#to_nfa_design calls #to_nfa_design on other objects—so it also works for more deeply nested cases like the regular expression abc, which contains two concatenations (a concatenated with b concatenated with c):

>> pattern =
     Concatenate.new(
       Literal.new('a'),
       Concatenate.new(Literal.new('b'), Literal.new('c'))
     )
=> /abc/
>> pattern.matches?('a')
=> false
>> pattern.matches?('ab')
=> false
>> pattern.matches?('abc')
=> true

We can use a similar strategy to convert a Choose expression into an NFA. In the simplest case, the NFAs for the regular expressions a and b can be combined to build an NFA for the regular expression a|b by adding a new start state and using free moves to connect it to the previous start states of the two original machines:

Before the a|b NFA has read any input, it can use a free move to go into either of the original machines’ start states, from which point it can read either 'a' or 'b' to reach an accept state. Again, it’s just as easy to glue together any two machines by adding a new start state and two free moves:

In this case, the ingredients for the combined machine are:

Again, this is easy to implement as Choose#to_nfa_design:

class Choose
  def to_nfa_design
    first_nfa_design = first.to_nfa_design
    second_nfa_design = second.to_nfa_design

    start_state = Object.new
    accept_states = first_nfa_design.accept_states + second_nfa_design.accept_states
    rules = first_nfa_design.rulebook.rules + second_nfa_design.rulebook.rules
    extra_rules = [first_nfa_design, second_nfa_design].map { |nfa_design|
      FARule.new(start_state, nil, nfa_design.start_state)
    }
    rulebook = NFARulebook.new(rules + extra_rules)

    NFADesign.new(start_state, accept_states, rulebook)
  end
end

The implementation works nicely:

>> pattern = Choose.new(Literal.new('a'), Literal.new('b'))
=> /a|b/
>> pattern.matches?('a')
=> true
>> pattern.matches?('b')
=> true
>> pattern.matches?('c')
=> false

And finally, repetition: how can we turn an NFA that matches a string exactly once into an NFA that matches the same string zero or more times? We can build an NFA for a* by starting with the NFA for a and making two additions:

Here’s how that looks:

The free move from the old accept state to the old start state allows the machine to match several times instead of just once ('aa', 'aaa', etc.), and the new start state allows it to match the empty string without affecting what other strings it can accept.^[24] We can do the same for any NFA as long as we connect each old accept state to the old start state with a free move:

This time we need:

Let’s turn that into code:

class Repeat
  def to_nfa_design
    pattern_nfa_design = pattern.to_nfa_design

    start_state = Object.new
    accept_states = pattern_nfa_design.accept_states + [start_state]
    rules = pattern_nfa_design.rulebook.rules
    extra_rules =
      pattern_nfa_design.accept_states.map { |accept_state|
        FARule.new(accept_state, nil, pattern_nfa_design.start_state)
      } +
      [FARule.new(start_state, nil, pattern_nfa_design.start_state)]
    rulebook = NFARulebook.new(rules + extra_rules)

    NFADesign.new(start_state, accept_states, rulebook)
  end
end

And check that it works:

>> pattern = Repeat.new(Literal.new('a'))
=> /a*/
>> pattern.matches?('')
=> true
>> pattern.matches?('a')
=> true
>> pattern.matches?('aaaa')
=> true
>> pattern.matches?('b')
=> false

Now that we have #to_nfa_design implementations for each class of regular expression syntax, we can build up complex patterns and use them to match strings:

>> pattern =
     Repeat.new(
       Concatenate.new(
         Literal.new('a'),
         Choose.new(Empty.new, Literal.new('b'))
       )
     )
=> /(a(|b))*/
>> pattern.matches?('')
=> true
>> pattern.matches?('a')
=> true
>> pattern.matches?('ab')
=> true
>> pattern.matches?('aba')
=> true
>> pattern.matches?('abab')
=> true
>> pattern.matches?('abaab')
=> true
>> pattern.matches?('abba')
=> false

This is a nice result. We began with a syntax for patterns and have now given a semantics for that syntax by showing how to convert any pattern into an NFA, a kind of abstract machine that we already know how to execute. In conjunction with a parser, this gives us a practical way of reading a regular expression and deciding whether it matches a particular string. Free moves are useful for this conversion because they provide an unobtrusive way to glue together smaller machines into larger ones without affecting the behavior of any of the components.

We’ve almost built a complete (albeit basic) regular expression implementation. The only missing piece is a parser for pattern syntax: it would be much more convenient if we could just write (a(|b))* instead of building the abstract syntax tree manually with Repeat.new(Concatenate.new(Literal.new('a'), Choose.new(Empty.new, Literal.new('b')))). We saw in Implementing Parsers that it’s not difficult to use Treetop to generate a parser that can automatically transform raw syntax into an AST, so let’s do that here to finish off our implementation.

Here’s a Treetop grammar for simple regular expressions:

grammar Pattern
  rule choose
    first:concatenate_or_empty '|' rest:choose {
      def to_ast
        Choose.new(first.to_ast, rest.to_ast)
      end
    }
    /
    concatenate_or_empty
  end

  rule concatenate_or_empty
    concatenate / empty
  end

  rule concatenate
    first:repeat rest:concatenate {
      def to_ast
        Concatenate.new(first.to_ast, rest.to_ast)
      end
    }
    /
    repeat
  end

  rule empty
    '' {
      def to_ast
        Empty.new
      end
    }
  end

  rule repeat
    brackets '*' {
      def to_ast
        Repeat.new(brackets.to_ast)
      end
    }
    /
    brackets
  end

  rule brackets
    '(' choose ')' {
      def to_ast
        choose.to_ast
      end
    }
    /
    literal
  end

  rule literal
    [a-z] {
      def to_ast
        Literal.new(text_value)
      end
    }
  end
end

Now we have all the pieces we need to parse a regular expression, turn it into an abstract syntax tree, and use it to match strings:

>> require 'treetop'
=> true
>> Treetop.load('pattern')
=> PatternParser
>> parse_tree = PatternParser.new.parse('(a(|b))*')
=> SyntaxNode+Repeat1+Repeat0 offset=0, "(a(|b))*" (to_ast,brackets):
     SyntaxNode+Brackets1+Brackets0 offset=0, "(a(|b))" (to_ast,choose):
       SyntaxNode offset=0, "("
       SyntaxNode+Concatenate1+Concatenate0 offset=1, "a(|b)" (to_ast,first,rest):
         SyntaxNode+Literal0 offset=1, "a" (to_ast)
         SyntaxNode+Brackets1+Brackets0 offset=2, "(|b)" (to_ast,choose):
           SyntaxNode offset=2, "("
           SyntaxNode+Choose1+Choose0 offset=3, "|b" (to_ast,first,rest):
             SyntaxNode+Empty0 offset=3, "" (to_ast)
             SyntaxNode offset=3, "|"
             SyntaxNode+Literal0 offset=4, "b" (to_ast)
           SyntaxNode offset=5, ")"
       SyntaxNode offset=6, ")"
     SyntaxNode offset=7, "*"
>> pattern = parse_tree.to_ast
=> /(a(|b))*/
>> pattern.matches?('abaab')
=> true
>> pattern.matches?('abba')
=> false