TRANSITION GRAPHS - UPSC FEVER

We could build an FA that accepts only the word baa.

The example we gave required five states primarily because an FA can read only one letter from the input string at a time.

Suppose we designed a more powerful machine that could read either one or two letters of the input string at a time and could change its state based on this information.

We might design a machine like the one below:

Since when we say "build a machine" all we have to do is scribble on paper-we do not have to solder, weld and screw-we could easily change the rules of what constitutes a machine and allow such pictures as the one above.

The objects we deal with in this book are mathematical models, which we shall discover are abstractions and simplifications of how certain actual machines do work.

This new rule for making models will also turn out to be practical. It will make it easier for us to design machines that accept certain different languages.

The machine above can read from the input string either one letter or two letters at a time, depending on which state it is in.

Notice that in this machine an edge may have several labels separated by commas just as in FA's, indicating that the edge can be traveled on if the input letters are any of the indicated combinations.

If we are interested in a machine that accepts only the word baa, why stop at assuming that the machine can read just two letters at a time?

A machine that accepts this word and that can read up to three letters at a time from the input string could be built with even fewer states.

If we hypothesize that a machine can read one or two letters at a time, then one can be built using only two states that can recognize all words that contain a doubled letter.

If we are going to bend the rules to allow for a machine like the last one, we must realize that we have changed something more fundamental than just the way the edges are labeled or the number of letters read at a time.

This last machine makes us exercise some choice in its running. We must decide how many letters to read from the input string each time we go back for more. This decision is quite important.

Let us say, for example, that the input string is baa. It is easy to see how this string can be accepted by this machine.

We first read in the letter b, which leaves us back at the start state by taking the loop on the left. Then we decide to read in both letters aa at once, which allows us to take the highway to the final state where we end.

However, if after reading in the single character b we then decided to read in the single character a, we would loop back and be stuck at the start state again.

When the third letter is read in, we would still be at the starting post. We could not then accept this string. There are two different paths that the input baa can take through the machine. This is totally different from the situation we had before, especially since one path leads to acceptance and one to rejection.

Another bad thing that might have happened is that we could have started processing the string baa by reading the first two letters at once. Since ba is not a double, we could not move to the final state.

In fact, when we read in ba, no edge tells us where to go, since ba is not the label of any edge leaving the start state.

The processing of this string breaks down at this point. When there is no edge leaving a state corresponding to the group of input letters that have been read while in that state, we say that the input crashes.

It also means that the input string is not accepted, but for a different reason than simply ending its path peacefully in a state that is not a final state.

The result of these considerations is that if we are going to change the definition of our abstract machine to allow for more than one letter to be read in at a time, we must also change the definition of acceptance.

We have to say that a string is accepted by a machine if there is some way it could be processed so as to arrive at a final state.

There may also be ways in which this string does not get to a final state, but we ignore all failures. We are about to create machines in which any edge in the picture can be labeled by any string of alphabet letters, but first we must consider the consequences.

We could now encounter the following additional problem:

On this machine we can accept the word baab in two different ways. First, we could take ba from the start state to state 1 and then ab would take us to the final state.

Or else we could read in the three letters baa and go to state 2 from which the final letter, b, would take us to the final state.

Previously, when we were dealing only with FA's, we had a unique path through the machine for every input string. Now some strings have no paths at all while some have several.

What is this machine going to do with the input string aaa? There is no way to process this string (reading any grouping of letters at a time) that will allow us to get to the final state. Therefore, this string cannot be accepted by this machine.

We use the word "rejected" to describe what must happen to this string.

This rejection is different from the situation for the string baa, which, though it doesn't reach the final state, can at least be fully processed to arrive at some state. However, we are not yet interested in the different reasons for failure and we use the word "rejection" for both cases.

We now have observed many of the difficulties inherent in expanding our definition of "machine" to allow word-labeled edges (or, equivalently, to reading more than one letter of input at a time).

We shall leave the definition of finite automation alone and call these new machines transition graphs because they are more easily understood as graphs than as tables.

A transition graph, abbreviated TG, is a collection of three things:

A finite set of states at least one of which is designated as the start state (-) and some (maybe none) of which are designated as final states (+).

An alphabet Σ of possible input letters from which input strings are formed.

A finite set of transitions that show how to go from one state to another based on reading specified substrings of input letters (possibly even the null string Λ ).

When we give a pictorial representation of a transition graph, clause 3 in the definition means that every edge is labeled by some string of letters not necessarily to only one letter.

We are also not requiring that there be any specific number of edges emanating from every state. Some states may have no edge coming out of them at all, and some may have thousands (for example, edges labeled a, aa, aaa, aaaa, . . ).

A successful path through a transition graph is a series of edges forming a path beginning at some start state (there may be several) and ending at a final state.

If we concatenate in order the strings of letters that label each edge in the path, we produce a word that is accepted by this machine.

The path from state 1 to state 2 to state 3 back to state 1 then to state 4 corresponds to the string (abb)(Λ)(aa)(b) .

This is one way of factoring the word abbaab, which, we now see, is accepted by this machine. Some other words accepted are abba, abbaaabba, and b .

When an edge is labeled with the string Λ , it means that we can take the ride it offers free (without consuming any letters from the input string).

Remember that we do not have to follow that edge, but we can if we want to.

If we are presented with a particular string of a's and b's to run on a given TG , we must decide how to break the word into substrings that might correspond to the labels of edges in a path.

If we consider the input string abbab for the machine above, we see that from state 1 , where we must start, we can proceed along the outgoing edge labeled abb or the one labeled b.

This word then moves along the edge from state 1 to state 2. The input letters abb are read and consumed.

What is left of the input string is ab, and we are now in state 2. From state 2 we must move to state 3 along the A-edge. At state 3 we cannot read aa, so we must read only a and go to state 4.

Here we have a b left in the input string but no edge to follow, so we must crash and reject the input string abbab .

Because we have allowed some edges to be traversed for free , we have also allowed for the possibility of more than one start state.

The reason we say that these two points are related is that we could always introduce more start states if we wanted to , simply by connecting them to the original start state by edges labeled Λ.

Examples of TRANSITION GRAPHS

There is no difference between the TG given above.

All the strings accepted by the first are accepted by the second and vice versa.

There are differences between the two machines such as the number of total states they have, but as language acceptors they are equivalent.

It is extremely important for us to understand that every FA is also a TG.

This means that any picture that represents an FA can be interpreted as a picture of a TG. Of course, not every TG satisfies the definition of an FA.

The picture (A) above represents a TG that accepts nothing, not even the null string Λ.

To be able to accept anything, it must have a final state.

The machine (B) accepts only the string Λ. Any other string cannot have a successful path to the final state through labels of edges since there are no edges (and hence no labels).

Any TG in which some start state is also a final state will always accept the string Λ this is also true of FA's.

There are some other TG's that accept the word Λ, for example: This machine accepts only the words Λ, baa, and abba.

Anything read while in the + state will cause a crash, since the + state has no outgoing edges.

Q. Consider the following TG

We can read all the input letters one at a time and stay in the left-side state.

When we read a 'b' in the - state there are two possible edges we can follow.

If the very last letter is a b, we can use it to go to the + state.

It must be the very last letter, since once in the right-side state if we try to read another letter we crash.

Notice that it is also possible to start with a word that does end with a b but to follow an unsuccessful path that does not lead to acceptance.

We could either make the mistake of following the non-loop b-edge too soon (on a non-final b) in which case we crash on the next letter; or else we might make the mistake of looping back to - when we read the last b, in which case we reject without crashing.

But still, all words that end in b can be accepted by some path, and that is all that is required.