Closure and nondeterminism

Some finite state machines are closed under certain operations such that if you can derive a machine for one set then you can also derive the machine for its compliment; If this is true, we say that these finite state machines are 'closed under compliment'.

If we have a particular set of strings and are not sure if they are regular or not, regular meaning that there exists a finite state machine that can define the set, said to be regular due to the nature of their growth in regular intervals.

Regular sets are closed under certain operations; The more of these closed operations that we know about, the easier it will be to determine whether a set is regular or not. We have looked at compliments already and a little towards reversal, we will examine these aspects more deeply now, adding to this tool set unions and intersections, so as to be better equipped to ascertain which sets are acceptable as regular and which are not.

Every 1 has at least two 0's following immediately after.

This is another example of a finite state machine, this time we will attempt to establish also the reverse of this language. To establish the reverse of this language we will define a string in which every 1 is preceded by at least two 0's. Starting out with this reversed string would have appeared to be a lot harder than our first string, demonstrating how reversal can be useful in determining the nature of a string.

Our instinct for the first string is that we might not be able to do it, however as we will see, knowing a finite state machine for a set allows you to work out the finite state machine for its reversal, makes the problem a lot easier to solve; We are able to solve it mechanically from the solution to the reversed string; This is an advantage to understanding these closure properties, in so doing we will also come up with nondeterminism again.

Although this finite state machine is correct it is not as compact as it could be, there are an infinite number of state machines that could accept the set, but only one that is the most refined; The two ending states in the first example are identical, as such one of them can be removed.

The reversal

every 1 has at least two 0's preceding it.

The reverse of a language of strings, is defined by taking every string within that language and reversing it; The new set is the reverse of the language.

Finite state machines of regular sets are always closed under reversal, it is always possible to generate a valid finite state machine by reversing another valid machine, due to this property.

The reversal of a machine introduces nondeterminism wonderfully, as we will need to pass through this state before finding our inverted deterministic finite state machine.

For the reversal of the machine above we will use the slightly more complicated of the two machines, it will be easier to deal with the reverse states with two starting seen in the first example.

If we want to use the machine in the reverse order and are taking our machine as a template, rather than starting the machine on the left side as we are currently doing, we will could be starting on the right side. The first symbols that we will look at will be the symbols at the end of the strings, the ending states of the previous diagram. The final state of the new machine will therefor be the starting state of the old machine, the entire machine is running in reverse; We will take all of the arrows and turn them backwards. We will be starting at the old machines endpoints and accepting strings that end up at the old machines starting point. The new final state is the old initial state and the new initial state will be both of the old final states.

Our new machine will look strange, it will be a nondeterministic finite state machine, we will have to interpret this machine and turn it back into a deterministic machine using the techniques that we have already learned.

Included in the drawing of the new machine is the section of its reversed machine that was the dead states from failed strings, this section of the new machine need not have been included in the drawing, however it is interesting to note that the reversal of machines can lead to the creation of strongly connected components that have no connection to the starting state, leading to the cutting out of sections of the graph. It is an advantage of reversal that sometimes large pieces of existing machines are cut out.

Our new final state is the old start state from the inverse machine.

From this non deterministic finite state machine we can now derive a deterministic finite state machine, using the algorithmic process of recording every possible state that the non deterministic machine can be in within each state of the deterministic machine.

The nondeterministic machine will have only one final state, it is the stating state of our initial machine during reversal, for a nondeterministic finite state machine there is never any reason to have any more than one final state.

Whereas the final deterministic machine will usually have more than one final state. Were we to insist that a finite state machine have only one final state, we would effectively limit the number of strings in the machines set, finding only a subset of the initial set.

The process that we have just performed to reverse the machine is completely general, it can be done to any machine; Therefor this example is essentially a proof that regular sets are closed under reversal. It is not the easiest way to prove this but never the less, it is worth baring in mind whilst performing the operation.

Any state in the resulting machine that contains the final A state from the initial machine is a final state in this machine. This machine also accepts the empty string and as such the start state is also circled.

This is a deterministic machine that for all strings, in front of every 1 there are at least two 0's.

The start state and the state A,D are effectively interchangeable, and we could more simply start at A,D.

There is no notion of a minimum nondeterministic machine, as there is for a deterministic machine. For nondeterministic machines, there may be many different machines that all have the same number of minimum states. There are cases for which the number of states are greatly increased by the reversal process, the number of states can increase from n to 2^n.

Their also exists a process by which a machine is simplified by this reversal process, by reversing the machine twice, if we are careful to remove all of the states that can no longer be reached, the resulting machine can be greatly reduced from that of the original machine. This method is not readily applied due to the exponential explosion of state that more frequently occurs. There is a better method for achieving the same, there exists a polynomial method that uses a dynamic programming strategy to achieve the same.

Closure

Union

Regular sets are closed under all sorts of conditions, and reversal is a tough proof of this, now we will look at a condition that is a little easier, the union. Consider two sets, the set of strings with an even number of 0's and another set of strings containing 101, both are regular sets that have finite state machines.

What is the finite state machine that is a union of two different conditions, that defines strings that either have and even number of 0's or the sub sting 101.

Because we know that nondeterminism is equivalent to determinism we can convert this nondeterministic machine into a deterministic one. In so doing we would inevitably take the product of the two machines. All this does is to pair the two states together, in a similar way to the compilation of a deterministic machine from a nondeterministic one. As such we do not really need to know about the product to convert the machines, we can simply follow the same process that we have using so far; Building upon the fact that we know that nondeterminism is equivalent to determinism.

Concatenation

Suppose now that we would like to find a string who's first part is made up of an even number of 0's and who's second part contains 101, that the sting that we now seek is a concatenation of the previous two machines.

We would create the first machine and then from the final state of that machine add and e move to the starting state of the second machine. The e move is the 'guess' as to when to jump over to the second machine, were we to loose nondeterminism in this case, we risk having a very complicated deterministic machine.

The first machine must satisfy its condition before the ϵ move can transfer over to the second condition, ensuring that it also be fulfilled.

Intersection

The same can apply for two machines A and B, we can devise a machine that will perform this intersection.

We compliment A and B, and then toggle the states, then union the results, it is complicated and there is work to be done, but it can be done. So now it is closed under intersection.

Union intersection and compliment are intrinsically tied together, you cannot every only have two of the three, if two of the three are closed, then the third is also.

This method of achieving an intersection is complicated, there are easier ways to do this, by this route there is a very high risk of an exponential growth of states.

There is a better method that we can employ to achieve the same result that is much simpler to use, which is to take the product of the two machines.

With two states in the first machine and four in the second, our machine can have anything up to eight states. Our final machine is tracking the states of both machines at the same time, the only state in the machine that corresponds the intersection of the two machines is the final state A,W.

The derived product of the two machines that signals acceptance upon arriving at the intersection of the final state of both.

Overview of the next step

Chomsky hierarchy

We have seen that there are nondeterministic and deterministic finite state machines and concluded that some of those machines are also regular expressions; Next we will prove that we can transform any nondeterministic finite state machine into a regular expression, and that any finite state machine can also be converted into a nondeterministic finite state machine.

Thus showing that regular expressions are identical to finite state machines.

Three views into exactly the same thing, this is essential in computer science, depending upon the different view or perspective that you have, certain things become more or less easier to perceive and thus to understand.

There is a fourth notion that also applies here, known as regular grammar or linear grammars. These are also equivalent to the same, we will demonstrate this equivalence also exists by comparing them to deterministic finite state machines.

This grammar to machine parallel is known as the Chomsky hierarchy.