Finite state automata

What I’m going to call a finite state automaton is more typically called a non-deterministic finite state automaton. Deterministic finite state automata, which will be considered in the next section, are a special case. I won’t use the word non-deterministic except for emphasis. Unless a finite state automaton is specifically stated to be deterministic you should not assume that it is. Most other authors follow the reverse convention, assuming finite state automata are deterministic unless specifically allowed to be non-deterministic.

Non-deterministic finite state automata

To specify a finite state automaton we need the following:

• A set \({ A }\) of tokens,
• A finite set \({ S }\) of states,
• A subset \({ I }\) of \({ S }\), the initial states,
• A subset \({ F }\) of \({ S }\), the accepting states, and
• A subset \({ T }\) of \({ S × A × S }\), the transition relation.

The interpretation of the ternary relation \({ T }\) is that \({ ( r , a , s ) ∈ T }\) if the automaton can transition to the state \({ s }\) when it reads an \({ a }\) while in state \({ r }\). The automaton must start in one of the states in \({ I }\). If it’s in one of the states in \({ F }\) at the end of the input then it halts successfully. It halts unsuccessfully if it is in a state not in \({ F }\) at the end of the input, or if it never reaches the end of the input because it reads a token in a state for which there is no transition allowed by \({ T }\). As with all the other forms of non-deterministic calculation we consider in this module the computation as whole is consider successful if some computational path is successful, even if others are not. In this case the finite state automaton is said to recognise the input. The set of lists of tokens recognised by a finite state automaton is said to be language recognised by it.

The non-determinism has two sources, the choice of initial state and the choice of the next state depending on the current state and the token just read. In most examples \({ I }\) has only one member and the first source of non-determinism is theoretical rather than real. Allowing multiple initial states is useful for the theory though, and sometimes in examples.

There is a traditional way of drawing diagrams for finite state automata, with directed graphs whose vertices are the states and whose edges indicate the allowed transitions, labelled to show which tokens allow that transition. The vertices in \({ F }\) are doubly circled. Those in \({ S ∖ F }\) are singly circled. Vertices in \({ I }\) are indicated by unlabeled incoming arrows which don’t come from any vertex. The accompanying diagrams show finite state automata which recognise the xy language and the language of integers.

You may have noticed a similarity between these finite state automata and the right regular grammars for these languages. In fact it’s possible to construct a finite state automaton from a right regular grammar by a purely mechanical procedure. The set \({ A }\) of tokens is the same as for the grammar. The set \({ S }\) of possible states is the set of non-terminal symbols of the grammar, except for the start symbol. The set \({ I }\) is the set of alternates for the start symbols. The set \({ F }\) is the set of non-terminals for which the empty list is an alternate. The set \({ T }\) consists of those \({ ( r , a , s ) }\) for which \({ a s }\) is an alternate for \({ r }\).

So every language which has a right regular grammar is recognised by a finite state automaton.

Given a finite state automaton for a language we can easily construct a finite state automaton for the reverse language. \({ A }\) and \({ S }\) are unchanged. The roles of \({ I }\) and \({ F }\) are reversed. The transition relation for the reversed grammar consists of those triples \({ ( r , a , s ) }\) for which \({ ( s , a , r ) }\) belongs to the transition relation for the original language. If we have a left regular grammar for a language then we can find a right regular grammar for the reversed language, use it to construct a finite state automaton for the reversed language, and then use the construction above to construct a finite state automaton for the doubly reversed language, which is the original language. So every language which has a left regular grammar is recognised by a finite state automaton.

Deterministic finite state automata

A finite state automaton is called deterministic if the set of initial states has at most one member and for any state \({ r }\) and token \({ a }\) there is at most one allowed transition, i.e. at most one \({ s ∈ S }\) such that \({ ( r , a , s ) ∈ T }\). A deterministic finite state automaton therefore has at most computational path.

It is sometimes useful to strengthen the requirement of at least one start state and at least one allowed transition in each state for each input token to exactly one start state and exactly one transition. The advantage of this is that it prevents the automaton from halting before it has read all of its input. I will call such automata strongly deterministic.

Our automaton above for the xy language is deterministic, and in fact strongly deterministic. Our automaton for the language of integers is not deterministic, since it has multiple initial states. A more common reason for a finite state automaton to be non-deterministic is the existence of multiple allowed transitions from a particular state on a particular input but this automaton happens not to have that problem.

Deterministic finite automata might seem more useful computationally than non-deterministic ones. This is only partly true. Other things being equal it’s easier to work with a deterministic finite state automaton than a non-deterministic one, but other things are rarely equal. Often the simplest deterministic finite state automaton for a given language is much larger than the simplest non-deterministic one and it is therefore more efficient to accept the complications of non-determinism. It is nonetheless important, at least for theoretical purposes, to know that any language recognised by a finite state

Earlier I discussed how to take a finite state automaton which recognises a language and construct from it a finite state automaton which recognises the reversed language. This construction was simple, but it doesn’t generally construct deterministic finite state automata from deterministic finite state automata. automaton is recognised by some deterministic finite state automaton.

We’ve already discussed how to simulate non-deterministic computations with deterministic ones. In general this is done with trees whose branches represent computational paths. The computational path describes not just the current state of the computation but also how it was arrived at. For finite state automata this is overkill. The future evolution of the computation, including whether it can terminate successfully, depends only on the current state, so we only need to keep track of the possible states the automaton could be in at each point in the input.

To illustrate this, consider the non-deterministic finite state automaton for the integers given earlier, and consider the input -17. Initially, i.e. before any tokens are read, we are in one of the states zero, neg_int, or pos_int. We then read the token -. There are no transitions from the states zero or pos_int for this token and there is only one from neg_int so the only surviving computational path leaves us in pos_int. The next token is 1 and there is only one allowed transition from there so next we find ourselves in digits. Reading a 7 there leaves us in digits. At this point the input ends. We are in an accepting state so the computation is successful.

At each point in the input there is a set of states the computation could be in. This is initially the set \({ I }\) of initial states. The computation succeeds if one of the states it could be in at the end of the input is accepting, i.e. if the set of possible states has non-empty intersection with \({ F }\). For each input token and set of states the system could be in before reading it we can compute the set of states it could be in after reading it by checking the allowed transitions for that token for each state.

The considerations above suggest the following power set construction. Given a non-deterministic finite state automaton described by a set of tokens \({ A }\), a set of states \({ S }\), a set of initial states \({ I }\), a set of accepting states \({ F }\) and a transition relation \({ T }\) we construct a deterministic finite state automaton with the same set of tokens \({ A }\), a set of states \({ S ' }\), a set of initial states \({ I ' }\), a set of accepting states \({ F ' }\) and a transition relation \({ T ' }\) according to the following rules.

• \({ S ' = P S }\), the power set of \({ S }\).
• \({ I ' = \{ I \} }\), the set with a single element, which is \({ I }\).
• \({ F ' = \{ B ∈ P S : B ∩ F ≠ ∅ \} }\), the set of subsets of \({ S }\) whose intersection with \({ F }\) is non-empty.
• \({ T ' = \{ ( B , a , C ) ∈ P S × A × P S : C = \{ s ∈ S : ∃ r ∈ B : ( r , a , s ) ∈ T \} \} }\). In other words \({ C }\) is the set of states to which there is an allowed transition on the input token \({ a }\) from a state in \({ B }\).

This is indeed a deterministic finite state automaton because its set of initial states has only one element and for any \({ B ∈ S ' }\) and \({ a ∈ A }\) there is only one \({ C ∈ S ' }\) such that \({ ( B , a , C ) ∈ T ' }\). At every point in the input the state of this automaton is the set of states the origin non-deterministic automaton could be in at the same point in the input. The deterministic automaton terminates successfully if and only if the non-deterministic one could terminate successfully. So they recognise the same language.

The construction above is called the power set construction, because the state space for the constructed automaton is the power set of the state space of the original automaton.

At this point I should give you an example of the construction but it’s hard to find reasonable examples. Our automaton for the xy language is already deterministic. We could still apply the power set construction to it, obtaining a new automaton with eight states, but there’s no point. Our finite state automaton for the integer language is genuinely non-deterministic so the power set construction does serve a purpose for it, but it gives us an automaton with 32 states. That’s certainly implementable on a computer but its diagram wouldn’t fit on a single page.