Theory of computation

The theory of computing is the science of computation, fundamental for the computer scientist; What can we really compute mechanically; How fast can we do it, and how much memory is required. There are many applications that emerge from this subject, including all of complier design and the theory of writing compilers and writing programs to translate languages; All of which emerge from the theory of computation.

Some of the models of computation that will be discussed will, as a side effect, help us to write compilers. When a computer is modelled, the architecture of the CPU is modelled with a finite state machine. All string searching in a text editor, also uses a finite state machine.

When you do any compiling or design a language such as XML, you describe it with a grammar, that grammar is the next level of model of computation. We will be discussing exactly that, the different models of computation that can be used to compute.

The things that we will be considering to compute will only require a boolean yes or no response from the machine and as such all those things that we will analyse can be thought of in terms of sets. We will define alphabets, of differing types and from those alphabets we will construct strings to compute, to search along or iterate over.

Finite State Machines

Hierarchy

Languages can be defined in three ways, by a machine by a grammar or by an expression.

Ask yourself, "can I write a program to solve this problem using a finite amount of memory", this will tell you whether or not you can use a finite state machine to solve a problem.

Every finite state machine works upon a predefined alphabet, the most simple of which is binary.

How to define a FSM

• Define a semantic meaning for each state.
• For every state you should have one arrow leaving that state for each letter of your alphabet.
• It is far better to first define all of the states.

Adding the arrows.

There is always one arrow pointing from nothing to one of the states; This arrow defines that state as the start.

The final state.

The final state must also be defined, this can be done with a double circle.

An even number of 0's

An even number of 1's and even number of 0's

First define the set of states, all possible combination of 0's and 1's in which the number of both are even. As we can see when considering two bits with discrete math, there are a total four possible states. We can represent these states with the letters EE for even 1 even 0, EO, OE, and OO consecutively for even 0's odd 1's, odd 1's even 0's and then finally odd 0's odd 1's. More clearly depicted by this state machine diagram.

Binary numbers that are divisible by four.

To check whether a binary number is divisible by four we need to check that the last two bits of the string are 0. To first demonstrate a simple case, it is easier to write a machine that checks only the first two bits. Notice the state D denoting a dead machine that has failed to complete and has halted.

This machine finds strings that start with two 0's, which is not what we want, but it gives us an idea of what we need to do.

To simplify things we have made a machine that signals the solved state every time that two consecutive 0's are encountered; However we are not starting in the right place in order to find those bits at the end of a string; For this machine to work, we will need to start at the final state. So how do we make a machine that will find strings that end with two 0's?

By moving the start arrow to the end of the chain, we insure that the 0 bits are sought last and not at the beginning. A few further modifications are required so that the machine will function as required; We no longer accept empty strings, nor single 0's

The trick here in solving was to reverse the process of the machine so as to find a simple way to deal with the problem, we should always consider that any solvable finite state machine has an inverse of itself problematically; These reflections are known as closure machines, or compliments.

Closures, compliments, closed under compliment

Any set that has a finite state machine that accepts it, is known as a regular set. Regular sets are closed under certain kinds of operations; Which means that if we perform the operation upon the set, giving a new set, for example were we to compliment, from a set we calculate everything that is not in that set, we have performed an operation upon that set to derive its compliment. If that new set is always also a regular set, without any exceptions, then we say that the collection of regular sets are closed under compliment.

If we were to devise a finite state machine for all of the strings that are not divisible by four, we could simply take our machine and toggle all of its current states. This simple fact is proof that if you are able to demonstrate that a set is finite, thus regular for one problem, you can also show that the same is true for its compliment by simply toggling the state of its nodes.

The proof really is that simple. Take any finite state machine defining a language of strings, for which we wish to find its compliment; All that need be done is to toggle the states; The two sets are said to be, closed under compliment.

Contains 110110

To find a machine that deals with a longer string, first we require a series of states that represents that string. The symbols used in describing the matching of strings is different in different books and schools, some using ε epsilon and others λ lambda, to denote the null or nil value; Otherwise said, no state. The process of building up the machine this way is algorithmic, the algorithm for which is known as the 'Knuth Morris Pratt algorithm'. We will use ε to denote our null state, the state that exists before staring; The reason for this will become clear as we continue on.

It is easy to follow the construction of this machine, observe how each state is described by, and grows in accordance with the denomination of the arrow that precedes it. Conversely, any arrow not having the correct value to continue, leads back to the nearest state that does assume its new structure.

Reversal becomes non deterministic

To find the reverse string of a previously constructed finite state machines target, we invert all of the arrows in its chain of states; Then transform its final state into its start state, and its start state into its final state. In so doing, we soon notice that the newly created finite state machine makes no sense; Our first node has two choices emerging from it, to where there were previously several state nodes converging upon its end. Although this facet of the reversal is not yet of any use to us; We will soon find this to be the beginnings of a non deterministic finite state machine.

This notion can be somewhat peculiar to comprehend, I only urge that you to continue on, should it be that you are finding this difficult to digest; The next few examples will lead up to a demonstration of this principle in practice, that is far simpler than it might first appear.

Every 1 followed by at least two 0's

This machine expands quite naturally from left to right. On arriving at the final state, upon closer inspection it can be seen that the final state is nothing but a repetition of the starting state, due to the recursive nature of the problem at hand.

We should be aware that their may exist a solution that is more efficient than that which first appears, once all duplicate states have been removed.

Not divisible by 3

For this problem it is not so simple as looking at the state of the last bit, as was the case for division by two; Division as a computation requires space. The space required grows with the complexity of the solution in a manor that is proportional to the log of the length of the string that is under examination. Without the use of memory we cannot achieve this feat. However, all that we require to solve our current problem is the remainder and not the full solution of a division; Finding the remainder is achievable with a finite state machine.

To calculate the remainder we will require three states; Remainder of one, two and zero or no remainder; The modulo results of the remainder of this division, will be the three states of of our machine.

For the string 1 the remainder would be 1 (1%3 = 1), if we concatenate a 0 to the string to get 10, we need add no remainder for the 0 itself but we will have to double the current value due to the effect of the binary left shift operation, giving us 2; As such the remainder is now also 2 (2%3 = 2) and so on until we have covered the length of our string.

10111 is 23 in decimal and 23%3 is 2, continuing on through our machines calculation we can see that the same result is arrived at, as the next three letters of our sting are 1's and the string is simply looping over the 1 in the 3rd state, the value of which is 2.

Considering the above machine, the following issue arises: If we try to implement its reverse, a machine that seeks strings divisible by three. Which would be our start state; We have two that were the passing cases!

To reverse this particular machine requires a new blank starting state with two empty [ε|λ|e] transitions; Rendering our new machine non deterministic.

A finite state machine is limited, if it were not we would not require unbound memory within a computer and we would have no need of Turing machines. The simplest thing that cannot be achieved with a finite state machine is to count, it is not possible to count to an arbitrary number; Bound by a finite condition, we can only count as high as is the length of our machines state sub string.

Non deterministic finite state machines

Non deterministic state machines do not give us any more power in knowing which finite state machines we can compute, but they do give us the ability to define machines more easily; Improving our ability to recognise which are finite and which are not. For those machines that we are able to describe, having this greater level of abstraction makes this operation far easier to achieve.

When considering a non deterministic finite state machine, we will no longer reject a string if it fails to pass the machine once, due to the existence of choices in states, we must now consider every possible path through the machine, then only do we reject it, if none terminate with the machine in a completion state.

Returning to the previous example 110110 when seeking a string that contains this as a sub string anywhere within its length, that there be two choices for the initial 1 within the strings form, requires that we try every possible case for the machine as it passes through the equivalent state. Take the string 1111011000, the machine must be tried for every instance of 1 whilst in the initial ε state. To make this more compact are readable, we leave some state changes out of the diagram drawing a self referential loop instead.

Consider the inverse of this non deterministic machine, the nature of the initial condition will stop any such machine from functioning. Non deterministic machines cannot be inverted to get their compliment, not so easily as deterministic machines. In order to get the compliment, we must first convert it into a deterministic machine and then compliment it; By definition non deterministic state machines are asymmetric.

The main difference then between the finite state machine and the non deterministic finite state machine is one of procedure, the finite state machine can be thought of as a single process where as a non deterministic finite state machine is parallel.

Some refer to this parallelism as guessing, rather than suggesting the machine trying every single path; If a correct path leading to the final state exists, it is simply stated that we have guessed the correct one.

Converting non deterministic machines

By making a non deterministic machine that will end on two zeros, and converting that machine in a systematic way, we can show that any non deterministic finite state machine may be turned into a deterministic finite state machine. We can see that all non deterministic state machines may be converted into deterministic machines using the same method, and as such we can conclude that although non determinism affords us convenience, it brings no extra power to the machine.

The first state of this machine iterates trying every single possible way of running, until it arrives at the case which has the required ending.

This machine will only accept a string that ends with 00 and nothing else, it is easy to mistakenly leave extra cases, effectively permitting the machine to end in other ways; we must be very careful that this does not happen. It is implicitly assumed that all strings which still have remaining letters upon reaching the end, will go to an unwritten dead state and fail.

For a deterministic machine it would be required of us to draw a loop at the end, with an arrow of 0's returning back to the same state, we could have drawn this here and the non deterministic machine would still be correct, however this is not required, the correct path will eventually be taken, the goal here is the simplicity of the description.

Our next step is to transform this machine into a deterministic finite state machine using a process that is very logical.

The transformation

The first thing that to do when transforming a non deterministic machine into a deterministic machine is to label the states.

The next principle is fundamental and has applications within the entire hierarchy of finite state machines, as such we should take care to insure that we have fully understood it.

Once each of the states have been named, iterate over the machine states taking note of all of the possible paths that the machine could take, use this information to draw a new deterministic version of the machine, reflecting all of the possibilities of the original machine, adding states if required, arrows that lead back to prior states should the machine fail, midway if some useful piece of the desired string still remains, else back to the beginning in the case of complete failure.

Our new machine will not display any of the possible dead states of the non deterministic machine, they are not relevant to the deterministic machine either, it only accepts passing strings.

The string accepting state of our machine is C and as such it is the final state of our deterministic machine, it is also true that the machine, when in this state, might also be in either of A or B states, but as is the case for the non deterministic machine, all that is required in order to show that the string has passed, is that it be in this state when the string terminates.

We have not incurred any great cost whilst transforming our non deterministic machine into a deterministic one, in fact we have the same number of states after the operation as before starting. The worst case scenario for this procedure is 2^n states where n is the number of states in the original non deterministic machine. So the general trade off when converting from non deterministic to deterministic is a possible exponential growth of the number of states required by the machine.

At the current stage in our abstraction of computation, this is not yet any great cause for concern, the quantity remains finite. However, a little higher up in the abstraction model, we will see that this does become problematic; On the Turing layer, the exponential growth of state translates to an exponential growth in computation time required.