simplified automaton
Word acceptance is the primary function of an automaton. When a word is fed into an automaton at an initial state, it is accepted exactly when a final state is reached upon reading the last symbol of the word. So when a state does not contribute in anyway to word acceptance, it may be tossed out without changing the accepting power of the automaton.
Definition. Let be an automaton. A state is said to be reachable from a state , if for some word over , . A state is said to be accessible if it is reachable from a start state. A state is live or coaccessible if a final state can be reached from it. If a state is both accessible and live, then it is called useful.
Clearly, every start state is accessible, and every final state is live. The following is the state diagram of an automaton that illustrates the concepts defined above.
States are accessible, while states are live. So the useful states are and .
The automaton is said to be accessible if every state in is accessible, and is live if every state is live. is called simplified or trim if it is both accessible and live (every state is useful).
Proposition 1.
An automaton is equivalent (http://planetmath.org/EquivalentAutomata) to a simplified automaton iff it accepts at least one word.
Proof.
Suppose an automaton is equivalent to a simplified automaton . Then the set of start states of is non-empty, say containing a state . So is live, which means there is a word such that contains a final state, or that .
Conversely, suppose an automaton accepts a word . This means that there is a start state and a final state such that , so that both and are useful. Now, let be the subset (of ) all useful states in , and let , . Then neither nor is empty. Finally, let be the restriction of on the set , such that
Then the five-tuple is an automaton. Obviously, . On the other hand, the word above is accepted by . Since is arbitrary, we see that as a result. ∎
Remark. If we allow the start state set of an automaton to be empty, then every automaton can be simplified, whether or not it accepts any words.
In the example above, the automaton is equivalent to the following simplified automaton:
However, the construction in the proof shows that, given a deterministic automaton , the simplified automaton may not be determinstic. In the example above, is not deterministic because . With respect to deterministic automata, the best we can do is the following:
Proposition 2.
A deterministic automaton is equivalent (http://planetmath.org/EquivalentAutomata) to a deterministic accessible automaton.
The proof of this is very similar to the one given above, except , and now consist of all accessible states, and is just a restriction on the domain of , since if a state is accessible, so is any state in for any .
Again, referring the example above, is deterministic, and it is equivalent to the following deterministic accessible automaton:
The language accepted by the automaton is represented by the regular expression .
Title | simplified automaton |
Canonical name | SimplifiedAutomaton |
Date of creation | 2013-03-22 19:01:51 |
Last modified on | 2013-03-22 19:01:51 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 8 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 03D05 |
Classification | msc 68Q45 |
Synonym | trim automaton |
Synonym | coaccessible |
Related topic | ReducedAutomaton |
Defines | reachable |
Defines | accessible |
Defines | live |
Defines | useful |