Have you ever noticed that, when you are writing code in a text editor like VS code, it recognizes things like unmatched braces? And it also sometimes warns you, with an irritating red highlight, about the incorrect syntax that you have written?

If not, then think about it. That is after all a piece of code. How can you write code for such a task? What would be the underlying logic behind it?

These are the kinds of questions that you will face if you have to write a compiler for a programming language. Writing a compiler is not an easy task. It is bulky job that demands a significant amount of time and effort.

In this article, we are not going to talk about how to build compilers. But we will talk about a concept that is a core component of the compiler: Context Free Grammars.

Introduction

All the questions we asked earlier represent a problem that is significant to compiler design called Syntax Analysis. As the name suggests, the challenge is to analyze the syntax and see if it is correct or not. This is where we use Context Free Grammars. A Context Free Grammar is a set of rules that define a language.

Here, I would like to draw a distinction between Context Free Grammars and grammars for natural languages like English.

Context Free Grammars or CFGs define a formal language. Formal languages work strictly under the defined rules and their sentences are not influenced by the context. And that's where it gets the name context free.

Languages such as English fall under the category of Informal Languages since they are affected by context. They have many other features which a CFG cannot describe.

Even though CFGs cannot describe the context in the natural languages, they can still define the syntax and structure of sentences in these languages. In fact, that is the reason why the CFGs were introduced in the first place.

In this article we will attempt to generate English sentences using CFGs. We will learn how to describe the sentence structure and write rules for it. To do this, we will use a JavaScript library called Tracery which will generate sentences on the basis of rules we defined for our grammar.

Before we dive into the code and start writing the rules for the grammar, let's just discuss some basic terms that we will use in our CFG.

Terminals: These are the characters that make up the actual content of the final sentence. These can include words or letters depending on which of these is used as the basic building block of a sentence.

In our case we will use words as the basic building blocks of our sentences. So our terminals will include words such as "to", "from", "the", "car", "spaceship", "kittens" and so on.

Non Terminals: These are also called variables. These act as a sub language within the language defined by the grammar. Non terminals are placeholders for the terminals. We can use non terminals to generate different patterns of terminal symbols.

In our case we will use these Non terminals to generate noun phrases, verb phrases, different nouns, adjectives, verbs and so on.

Start Symbol: a start symbol is a special non terminal that represents the initial string that will be generated by the grammar.

Now that we know the terminology let's start learning about the grammatical rules.

While writing grammar rules, we will start by defining the set of terminals and a start state. As we learned before, that start symbol is a non-terminal. This means it will belong to the set of non-terminals.

T: ("Monkey", "banana", "ate", "the")
S: Start state.

And the rules are:

S --> nounPhrase verbPhrase
nounPhrase --> adj nounPhrase | adj noun
verbPhrase --> verb nounPhrase
adjective  --> the
noun --> Monkey | banana
verb --> ate

The above grammatical rules may seem somewhat cryptic at first. But if we look carefully, we can see a pattern that is being generated out of these rules.

A better way to think about the above rules is to visualise them in the form of a tree structure. In that tree we can put S in the root and nounPhrase and verbPhrase can be added as children of the root. We can proceed in the same way with nounPhrase and verbPhrase too. The tree will have terminals as its leaf nodes because that is where we end these derivations.

In the above image we can see that S (a nonterminal) derives two non terminals NP(nounPhrase) and VP(verbPhrase). In the case of NP, it has derived two non terminals, Adj and Noun.

If you look at the grammar, NP could also have chosen Adj and nounPhrase. While generating text, these choices are made randomly.

And finally the leaf nodes have terminals which are written in the bold text. So if you move from left to right, you can see that a sentence is formed.

The term often used for this tree is a Parse Tree. We can create another parse tree for a different sentence generated by this grammar in a similar way.

Now let's proceed further to the code. As I mentioned earlier, we will use a JavaScript library called Tracery for text generation using CFGs. We will also write some code in HTML and CSS for the front-end part.

The Code

Let's start by first getting the tracery library. You can clone the library from GitHub here. I have also left the link to the GitHub repository by galaxykate at the end of the article.

Before we use the library we will have to import it. We can do this simply in an HTML file like this.

<html>
    <head>
        <script src="tracery-master/js/vendor/jquery-1.11.2.min.js"></script>
        <script src="tracery-master/tracery.js"></script>
        <script src="tracery-master/js/grammars.js"></script>
        <script src='app.js'></script>
    </head>

</html>

I have added the cloned tracery file as a script in my HTML code. We will also have to add JQuery to our code because tracery depends on JQuery. Finally, I have added app.js which is the file where I will add rules for the grammar.

Once that is done, create a JavaScript file where we will define our grammar rules.

var rules = {
        "start": ["#NP# #VP#."],
        "NP": ["#Det# #N#", "#Det# #N# that #VP#", "#Det# #Adj# #N#"],
        "VP": ["#Vtrans# #NP#", "#Vintr#"],
        "Det": ["The", "This", "That"],
        "N": ["John Keating", "Bob Harris", "Bruce Wayne", "John Constantine", "Tony Stark", "John Wick", "Sherlock Holmes", "King Leonidas"],
        "Adj": ["cool", "lazy", "amazed", "sweet"],
        "Vtrans": ["computes", "examines", "helps", "prefers", "sends", "plays with", "messes up with"],
        "Vintr": ["coughs", "daydreams", "whines", "slobbers", "appears", "disappears", "exists", "cries", "laughs"]
    }

Here you will notice that the syntax for defining rules is not much different from how we defined our grammar earlier. There are very minor differences such as the way non-terminals are defined between the hash symbols. And also the way in which different derivations are written. Instead of using the "|" symbol for separating them, here we will put all the different derivations as different elements of an array. Other than that, we will use the semicolons instead of arrows to represent the transition.

This new grammar is a little more complicated than the one we defined earlier. This one includes many other things such as Determiners, Transitive Verbs and Intransitive Verbs. We do this to make the generated text look more natural.

Let's now call the tracery function "createGrammar" to create the grammar we just defined.

let grammar = tracery.createGrammar(rules);

This function will take the rules object and generate a grammar on the basis of these rules. After creating the grammar, we now want to generate some end result from it. To do that we will use a function called "flatten".

let expansion = grammar.flatten('#start#');

It will generate a random sentence based on the rules that we defined earlier. But let's not stop there. Let's also build a user interface for it. There's not much we will have to do for that part – we just need a button and some basic styles for the interface.

In the same HTML file where we added the libraries we will add some elements.

<html>
    <head>
        <title>Weird Sentences</title>
        <link rel="stylesheet" href="style.css"/>
        <link href="https://fonts.googleapis.com/css?family=UnifrakturMaguntia&display=swap" rel="stylesheet">
        <link href="https://fonts.googleapis.com/css?family=Harmattan&display=swap" rel="stylesheet">

        <script src="tracery-master/js/vendor/jquery-1.11.2.min.js"></script>
        <script src="tracery-master/tracery.js"></script>
        <script src="tracery-master/js/grammars.js"></script>
        <script src='app.js'></script>
    </head>
    <body>
        <h1 id="h1">Weird Sentences</h1>
        <button id="generate" onclick="generate()">Give me a Sentence!</button>
        <div id="sentences">

        </div>
    </body>
</html>

And finally we will add some styles to it.

body {
    text-align: center;
    margin: 0;
    font-family: 'Harmattan', sans-serif;
}

#h1 {
    font-family: 'UnifrakturMaguntia', cursive;
    font-size: 4em;
    background-color: rgb(37, 146, 235);
    color: white;
    padding: .5em;
    box-shadow: 1px 1px 1px 1px rgb(206, 204, 204);
}

#generate {
    font-family: 'Harmattan', sans-serif;
    font-size: 2em;
    font-weight: bold;
    padding: .5em;
    margin: .5em;
    box-shadow: 1px 1px 1px 1px rgb(206, 204, 204);
    background-color: rgb(255, 0, 64);
    color: white;
    border: none;
    border-radius: 2px;
    outline: none;
}

#sentences p {
    box-shadow: 1px 1px 1px 1px rgb(206, 204, 204);
    margin: 2em;
    margin-left: 15em;
    margin-right: 15em;
    padding: 2em;
    border-radius: 2px;
    font-size: 1.5em;
}

We will also have to add some more JavaScript to manipulate the interface.

let sentences = []
function generate() {
    var data = {
        "start": ["#NP# #VP#."],
        "NP": ["#Det# #N#", "#Det# #N# that #VP#", "#Det# #Adj# #N#"],
        "VP": ["#Vtrans# #NP#", "#Vintr#"],
        "Det": ["The", "This", "That"],
        "N": ["John Keating", "Bob Harris", "Bruce Wayne", "John Constantine", "Tony Stark", "John Wick", "Sherlock Holmes", "King Leonidas"],
        "Adj": ["cool", "lazy", "amazed", "sweet"],
        "Vtrans": ["computes", "examines", "helps", "prefers", "sends", "plays with", "messes up with"],
        "Vintr": ["coughs", "daydreams", "whines", "slobbers", "appears", "disappears", "exists", "cries", "laughs"]
    }

    let grammar = tracery.createGrammar(data);
    let expansion = grammar.flatten('#start#');

    sentences.push(expansion);

    printSentences(sentences);
}

function printSentences(sentences) {
    let textBox = document.getElementById("sentences");
    textBox.innerHTML = "";
    for(let i=sentences.length-1; i>=0; i--) {
        textBox.innerHTML += "<p>"+sentences[i]+"</p>"
    }
}

Once you have finished writing the code, run your HTML file. It should look something like this.

Every time you click the red button it will generate a sentence. Some of these sentences might not make any sense. This is because, as I said earlier, CFGs cannot describe the context and some other features that natural languages possess. It is used only to define the syntax and structure of the sentences.

You can check out the live version of this here.

Conclusion

If you have made it this far, I highly appreciate your resilience. It might be a new concept for some of you, and others might have learnt about it in their college courses. But still, Context Free Grammars have interesting applications that range widely from Computer Science to Linguistics.

I have tried my best to present the main ideas of CFGs here, but there is a lot more that you can learn about them. Here I have left links to some great resources:

• Context Free Grammars by Daniel Shiffman.
• Context Free Grammars Examples by Fullstack Academy
• Tracery by Galaxykate

Understanding the Finite State Machine

A FSM is defined by its states, its initial state and the transitions.

The power of FSM comes from the ability to clearly define different behaviors in different conditions. Usually FSM is used with looping behavioral scripts which constantly evaluate the current situation in a loop or with events.

To help form an image of how this might be applied, a coffee machine will be used as an example of a finite state machine. We will also cover a state diagram to visualise the FSM and provide coding examples.

State Diagram

This diagram shows three possible states for the coffee machine:

• Open
• ReadyToBuy
• PoweredOff

The lines between these states show which transitions are possible between states and in which direction. These transitions have conditions for when the FSM needs to change between states.

• StartUpMachine From the PoweredOff state to the Open state the machine has to start up. This is done manually in this case.
• deposit >= cost of coffee The FSM evaluates the amount of deposited cash either in a loop or when the amount changes (recommended in this case) If you deposit enough cash into the coffee machine, the FSM will go from ‘Open’ to ‘ReadyToBuy’.
• ShutdownMachine The machine will automatically go from Open to PoweredOff through the ShutDownMachine method if the condition ‘no more coffees left’ is met.
• DispenseCoffee In the ReadyToBuy state the user can buy a coffee whereafter it will be brewed and dispensed. The condition is when the BuyCoffee event (!Link to observer pattern!) fires. (not shown in diagram)
• CancelCoffee If the user opts to cancel, the machine will go from ReadyToBuy to Open.
• ShutDownMachine The machine will go to PoweredOff state

States

In every state there is defined behavior which will only be executed when the object is in that state. For instance, during PoweredOff the coffee machine won’t brew coffee before it’s powered on, during the Open state it will wait either until there’s enough cash inserted, until the power down command is given, or until it runs out of coffee. During this Open state it can do routines such as cleaning which won’t happen in other states.

Initial State

Every FSM has an initial state, this means which state it starts in when it is created and has to be defined when constructed or instantiated. Of course it’s possible to directly change state if conditions are met.

Transitions

Every state either constantly evaluates if it should transition to another state or will transition to another state based on a triggered event.

DFA and NFA

There are two types of finite automaton, Deterministic (DFA) and Nondeterministic (NFA). Both of them accept regular languages and operate more or less in the same way described above however with some differences.

A DFA accepts or rejects a string of symbols and only produces one unique computation or automaton for each input string. Deterministic refers to the uniqueness of the computation. A Finite State Machine is called a DFA if it obeys the following rules:

1. Each of its transitions is uniquely determined by its source state and input symbol
2. Reading an input symbol is required for each state transition.

An NFA does not need to obey these restrictions, meaning that each DFA is also an NFA. And since they both only recognize regular languages, each NFA can be converted into an equivalent DFA using the powerset construction algorithm.

So what sort of rules can we expect to find in NFAs but not DFAs ?

1. An NFA can have an empty string transition (generally denoted by an epsilon). Meaning that when at a certain state with an epsilon for a transition rule, the machine can transition to the next state without reading an input symbol
2. In an NFA, each pair of state and transition symbol can have multiple destination states as opposed to the unique destinations of pairs in DFAs
3. Each pair of state and transition symbol produces a ‘branch’ of computation for each of its possible destination creating some sort of a multithreaded system.
4. A DFA will reject the input string if it lands on any state other than the acceptance state. In an NFA, we only need one ‘branch’ to land on an acceptance state in order to accept the string.

If you want to learn more, here's a great in-depth guide on state machines.

Recently, I have written about simplifying an event sourced application.

The article starts with code from a talk by Jakub Pilimon and Kenny Bastani. And it ends with building a model for events in the code: how they are applied, and under which conditions.

The sample application is about Credit Card management. You can:

• Assign a credit limit. But only once, otherwise the application throws an IllegalStateException.
• Withdraw money. But you can't make more than 45 withdrawals in a certain cycle. Or you'll get an exception as well.
• Repay money

I played around with the CreditCard class. I had a feeling that something might be wrong with the withdraw method. So I wrote a test that checks for the correct behavior.

@Test(expected = IllegalStateException.class)
public void withdrawWithoutLimitAssignedThrowsIllegalStateException() {
    CreditCard card = new CreditCard(UUID.randomUUID());
    card.withdraw(BigDecimal.ZERO);
}

The test attempts to withdraw an amount of zero. But no credit limit has been assigned before. The application should reject this, and throw an IllegalStateException.
Instead, the application threw a NullPointerException.

The application assumed that the limit had been assigned before.
Now: this is a sample application. If it covered all cases it probably wouldn't be as understandable as it is.

Let's pretend we're dealing with a real world application. What if the required order of commands/events depends on a multitude of conditions and states?

If you have ever tried to implement this with conditional statements only, you probably know it's easy to lose the overview. But there is a standard solution for managing complicated flows and changes in behavior.

State machine to the rescue

In computer science, state machines have been around for decades. They are well understood in theory. They are battle proven in practice. They are the de facto standard for dealing with state dependent behavior.

So I decided to create a UML state machine model for the sample application. I asked myself first: Do I want to deal with commands or events in the state machine?

Commands are about something the application should do in the future.
Events are about something that has happened in the past.

I wanted to prevent withdrawals without a credit limit assigned.
So the state machine model needed to deal with commands.

The syntax of a transition in the diagram is command[condition] / commandHandler(). It means: when a command object has been received, and the condition is fulfilled if present, handle the command and go to the next state.

The model fixes what is allowed to happen, and what not. For example: repaying is only possible after withdrawing.

But that precision has a price. If you want the state machine model to be executed and to control the behavior at runtime, you need to model every possible transition from every state. Including its condition, if there are two transitions with the same event.

That's why there is a lot more repetition in the state machine than in the original code with the if statements. A way to reduce the amount of repetition is to use super states and sub states:

It is easy to define state dependent behavior in a state machine model. But a state independent rule like in any state (when condition X holds), do Y leads to several transitions. For example, I needed to add requestToCloseCycle to every super state.

You need people with the right skills to create the models. And it's not easy to communicate about the models with non-technical stakeholders. It's not the way they normally speak about user journeys.

Saying goodbye

It seems there are two options so far.

In the left corner: the if statement. Easy to start with. Low overhead. Best fit for applications that have no complicated flows of behavior. But it's easy to lose the overview when the behavior gets complicated.

In the right corner: the executable state machine model. Powerful. Proven. Precise. Gives you an overview of the behavior. But it's hard to define state independent rules. And state machine models are difficult to communicate about with non-technical stakeholders.

I stand in the third corner. I have found an alternative to state machines.
A solution that

• enables you to define conditions. But you don't have to in most cases.
• makes state dependent and independent rules equally easy to specify.
• uses language that all stakeholders can relate to.

Before I dig into the details, here's the sample state machine model rewritten using that solution:

Model model = Model.builder()
  .useCase(useCreditCard)
    .basicFlow()
        .step(assigningLimit).user(requestsToAssignLimit).systemPublish(assignedLimit)
        .step(withdrawingCard).user(requestsWithdrawingCard).systemPublish(withdrawnCard).reactWhile(accountIsOpen)
        .step(repaying).user(requestsRepay).systemPublish(repay).reactWhile(accountIsOpen)

    .flow("Withdraw again").after(repaying)
        .step(withdrawingCardAgain).user(requestsWithdrawingCard).systemPublish(withdrawnCard)
        .step(repeating).continuesAt(withdrawingCard)

    .flow("Cycle is over").anytime()
        .step(closingCycle).on(requestToCloseCycle).systemPublish(closedCycle)

    .flow("Limit can only be assigned once").condition(limitAlreadyAssigned)
        .step(assigningLimitTwice).user(requestsToAssignLimit).system(throwsAssignLimitException)

    .flow("Too many withdrawals").condition(tooManyWithdrawalsInCycle) 
        .step(withdrawingCardTooOften).user(requestsWithdrawingCard).system(throwsTooManyWithdrawalsException)
.build();
return model;

As you can see, the model is in the code. A model runner executes this model. The runner reacts to commands/events, similar to a state machine.

The basic flow is the "happy day scenario". The steps of a user to reach her goal. The other flows cover alternative and error scenarios.

A flow can define an explicit condition for its first step to run - e.g. after(...), anytime() or condition() in the sample.
If a flow has an explicit condition, the flow starts when the condition is fulfilled and the runner is currently in a different flow.
If a flow has no explicit condition (e.g. the basic flow in the sample), the first step runs after the runner has started, when no step has been run so far.

Starting with the second step of a flow, each step has an implicit condition. That condition is: run the step after the previous step in the same flow, unless a different flow with an explicit condition can start.
So in contrast to state machines, you don't need to specify the conditions after the first step.

Internally, state depending behavior is realized by checking a condition.
Every step contains its complete condition that defines exactly when the step can run. That's how requirements as code can treat state dependent and independent behavior alike.

Have a look at further examples to dig deeper.

When to use requirements as code

Many applications have dynamic internal behavior. This is true for distributed applications in particular. They need to deal with the fact that "the other party" is not available.

But from a user's perspective, these applications look quite predictable and regular. When I want to watch a show on Netflix or Amazon Prime, I follow the exact same steps each time until I can watch it. It looks like one step just follows the other.

That's the sweet spot for requirements as code, if used as an alternative to a state machine: defining the visible behavior of an application.

How the Credit Card application works now

• A client sends a command to the CreditCardAggregateRoot
• The CreditCardAggregateRoot uses the event repository to replay all the events for the credit card, to restore it
• The CreditCardAggregateRoot uses the above model to dispatch the command to a command handling method
• The command handling method produces an event and applies it to the CreditCard instance.
• The event handling model of the CreditCard instance dispatches the event to a state changing method

Conclusion

I hope you enjoyed my article. I also want to invite you to look at the library that I used throughout the article. Try it out in practice, and let me know the result.

If you want to keep up with what I'm doing or drop me a note, follow me on LinkedIn or Twitter. To learn about agile software development, visit my online course.
Last edited April 27, 2020: updated event sourcing process

An intro to Computer Science concepts

Computer science enables us to program, but it is possible to do a lot of programming without understanding the underlying computer science concepts.

This isn’t always a bad thing. When we program, we work at a much higher level of abstraction.

When we drive a car, we only concern ourselves with two or three pedals, a gearshift, and a steering wheel. You can safely operate a car without having any clear idea of how it works.

However, if you want to operate a car at the very limits of its capabilities, you need to know a lot more about automobiles than just the three pedals, gearshift and steering wheel.

The same is true of programming. A lot of everyday work can be accomplished with little or no understanding of computer science. You don’t need to understand computational theory to build a “Contact Us” form in PHP.

However, if you plan to write code that requires serious computation, you will need to understand a bit more about how computation works under the hood.

The purpose of this article is to provide some fundamental background for computation. If there is interest, I may follow up with some more advanced topics, but right now I want to look at the logic behind one of the simplest abstract computational devices — a finite state machine.

Finite State Machines

A finite state machine is a mathematical abstraction used to design algorithms.

In simpler terms, a state machine will read a series of inputs. When it reads an input, it will switch to a different state. Each state specifies which state to switch to, for a given input. This sounds complicated but it is really quite simple.

Imagine a device that reads a long piece of paper. For every inch of paper there is a single letter printed on it–either the letter ‘a’ or the letter ‘b’.

A paper tape, with eight letters printed on it

As the state machine reads each letter, it changes state. Here is a very simple state machine:

The circles are “states” that the machine can be in. The arrows are the transitions. So, if you are in state s and read an ‘a’, you’ll transition to state q. If you read a ‘b’, you’ll stay in state s.

So if we start on s and read the paper tape above from left to right, we will read the ‘a’ and move to state q.

Then, we’ll read ‘b’ and move back to state s.

Another ‘b’ will keep us on s, followed by an ‘a’ — which moves us back to the q state. Simple enough, but what’s the point?

Well, it turns out that you can run a tape through the state machine and tell something about the sequence of letters, by examining the state you end up on.

In our simple state machine above, if we end in state s, the tape must end with a letter ‘b’. If we end in state q, the tape ends with the letter ‘a’.

This may sound pointless, but there are an awful lot of problems that can be solved with this type of approach. A very simple example would be to determine if a page of HTML contains these tags in this order:

<html>   <head> </head>   <body> </body> </html>

The state machine can move to a state that shows it has read the html tag, loop until it gets to the head tag, loop until it gets to the head close tag, and so on.

If it successfully makes it to the final state, then you have those particular tags in the correct order.

Finite state machines can also be used to represent many other systems — such as the mechanics of a parking meter, pop machine, automated gas pump, and all kinds of other things.

Deterministic Finite State Machines

The state machines we’ve looked at so far are all deterministic state machines. From any state, there is only one transition for any allowed input. In other words, there can’t be two paths leading out of a state when you read the letter ‘a’. At first, this sounds silly to even make this distinction.

What good is a set of decisions if the same input can result in moving to more than one state? You can’t tell a computer, if x == true then execute doSomethingBig or execute doSomethingSmall, can you?

Well, you kind of can with a state machine.

The output of a state machine is its final state. It goes through all its processing, and then the final state is read, and then an action is taken. A state machine doesn’t do anything as it moves from state to state.

It processes, and when it gets to the end, the state is read and something external triggers the desired action (for example, dispensing a soda can). This is an important concept when it comes to non-deterministic finite state machines.

Non-deterministic Finite State Machines

Non-deterministic finite state machines are finite state machines where a given input from a particular state can lead to more than one different state.

For example, let’s say we want to build a finite state machine that can recognize strings of letters that:

• Start with the letter ‘a’
• and are then followed by zero or more occurrences of the letter ‘b’
• or, zero or more occurrences of the letter ‘c’
• are terminated by the next letter of the alphabet.

Valid strings would be:

• abbbbbbbbbc
• abbbc
• acccd
• acccccd
• ac (zero occurrences of b)
• ad (zero occurrences of c)

So it will recognize the letter ‘a’ followed by zero or more of the same letter of ‘b’ or ‘c’, followed by the next letter of the alphabet.

A very simple way to represent this is with a state machine that looks like the one below, where a final state of t means that the string was accepted and matches the pattern.

Pattern matching finite state machine

Do you see the problem? From starting point s, we don’t know which path to take. If we read the letter ‘a’, we don’t know whether to go to the state q or r.

There are a few ways to solve this problem. One is by backtracking. You simply take all the possible paths, and ignore or back out of the ones where you get stuck.

This is basically how most chess playing computers work. They look at all the possibilities — and all the possibilities of those possibilities — and choose the path that gives them the greatest number of advantages over their opponent.

The other option is to convert the non-deterministic machine into a deterministic machine.

One of the interesting attributes of a non-deterministic machine is that there exists an algorithm to turn any non-deterministic machine into a deterministic one. However, it is often much more complicated.

Fortunately for us, the example above is only slightly more complicated. In fact, this one is simple enough that we can transform it into a deterministic machine in our head, without the aid of a formal algorithm.

The machine below is a deterministic version of the non-deterministic machine above. In the machine below, a final state of t or v is reached by any string that is accepted by the machine.

A deterministic finite state machine

The non-deterministic model has four states and six transitions. The deterministic model has six states, ten transitions and two possible final states.

That isn’t that much more, but complexity usually grows exponentially. A moderately sized non-deterministic machine can produce an absolutely huge deterministic machine.

Regular Expressions

If you have done any type of programming, you’ve probably encountered regular expressions. Regular expressions and finite state machines are functionally equivalent. Anything you can accept or match with a regular expression, can be accepted or matched with a state machine.

For example, the pattern described above could be matched with the regular expression: a(b*c|c*d)

Regular expressions and finite state machines also have the same limitations. In particular, they both can only match or accept patterns that can be handled with finite memory.

So what type of patterns can’t they match? Let’s say you want to only match strings of ‘a’ and ‘b’, where there are a number of ‘a’s followed by an equal number of ‘b’s. Or n ‘a’s followed by n ‘b’s, where n is some number.

Examples would be:

• ab
• aabb
• aaaaaabbbbbb
• aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb

At first, this looks like an easy job for a finite state machine. The problem is that you’ll quickly run out of states, or you’ll have to assume an infinite number of states — at which point it is no longer a finite state machine.

Let’s say you create a finite state machine that can accept up to 20 ‘a’s followed by 20 ‘b’s. That works fine, until you get a string of 21 ‘a’s followed by 21 ‘b’s — at which point you will need to rewrite your machine to handle a longer string.

For any string you can recognize, there is one just a little bit longer that your machine can’t recognize because it runs out of memory.

This is known as the Pumping Lemma which basically says: “if your pattern has a section that can be repeated (like the one) above, then the pattern is not regular”.

In other words, neither a regular expression nor a finite state machine can be constructed that will recognize all the strings that do match the pattern.

If you look carefully, you’ll notice that this type of pattern where every ‘a’ has a matching ‘b’, looks very similar to HTML. Within any pair of tags, you may have any number of other matching pairs of tags.

So, while you may be able to use a regular expression or finite state machine to recognize if a page of HTML has the <html>, `; and elements in the correct order, you can’t use a regular expression to tell if an entire HTML page is valid or not — because HTML is not a regular pattern.

Turing Machines

So how do you recognize non-regular patterns?

There is a theoretical device that is similar to a state machine, called a Turing Machine. It is similar to a finite state machine in that it has a paper strip which it reads. But, a Turing Machine can erase and write on the paper tape.

Explaining a Turing Machine will take more space that we have here, but there are a few important points relevant to our discussion of finite state machines and regular expressions.

Turing Machines are computationally complete — meaning anything that can be computed, can be computed on a Turing Machine.

Since a Turing Machine can write as well as read from the paper tape, it is not limited to a finite number of states. The paper tape can be assumed to be infinite in length. Of course, actual computers don’t have an infinite amount of memory. But, they usually do contain enough memory so you don’t hit the limit for the type of problems they process.

Turing Machines give us an imaginary mechanical device that lets us visualize and understand how the computational process works. It is particularly useful in understanding the limits of computation. If there is interest I’ll do another article on Turing Machines in the future.

Why does this matter?

So, what’s the point? How is this going to help you create that next PHP form?

Regardless of their limitations, state machines are a very central concept to computing. In particular, it is significant that for any non-deterministic state machine you can design, there exists a deterministic state machine that does the same thing.

This is a key point, because it means you can design your algorithm in whichever way is the easiest to think about. Once you have a working algorithm, you can convert it into whatever form is most efficient.

The understanding that finite state machines and regular expressions are functionally equivalent opens up some incredibly interesting uses for regular expression engines — particularly when it comes to creating business rules that can be changed without recompiling a system.

A foundation in Computer Science allows you to take a problem you don’t know how to solve and reason: “I don’t know how to solve X, but I do know how to solve Y. And I know how to convert a solution for Y into a solution for X. Therefore, I now know how to solve X.”

If you like this article, you might enjoy my YouTube channel where I create an occasional video or cartoon about some aspect of creating software. I also have a mailing list for people who would like an occasional email when I produce something new.

Originally published at blog.markshead.com on February 11, 2018.