请输入您要查询的字词:

 

单词 SimplifiedAutomaton
释义

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 A=(S,Σ,δ,I,F) be an automaton. A state sS is said to be reachablePlanetmathPlanetmath from a state tS, if for some word u over Σ, tδ(s,u). 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 diagramMathworldPlanetmathPlanetmath of an automaton that illustrates the conceptsMathworldPlanetmath defined above.

States σ,p,r,s are accessible, while states σ,p,q are live. So the useful states are σ and p.

The automaton A is said to be accessible if every state in S is accessible, and is live if every state is live. A is called simplified or trim if it is both accessible and live (every state is useful).

Proposition 1.

An automaton is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath (http://planetmath.org/EquivalentAutomata) to a simplified automaton iff it accepts at least one word.

Proof.

Suppose an automaton A is equivalent to a simplified automaton A. Then the set of start states of A is non-empty, say containing a state q. So q is live, which means there is a word u such that δ(p,u) contains a final state, or that uL(A)=L(A).

Conversely, suppose an automaton A=(S,Σ,δ,I,F) accepts a word u. This means that there is a start state q and a final state r such that rδ(q,u), so that both q and r are useful. Now, let S be the subset (of S) all useful states in A, and let I=IS, F=FS. Then neither I nor F is empty. Finally, let δ be the restrictionPlanetmathPlanetmathPlanetmath of δ on the set S×Σ, such that

δ(s,a):=δ(s,a)S.

Then the five-tuple A:=(S,Σ,δ,I,F) is an automaton. Obviously, L(A)L(A). On the other hand, the word u above is accepted by A. Since u is arbitrary, we see that L(A)=L(A) 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 A, the simplified automaton A may not be determinstic. In the example above, A is not deterministicMathworldPlanetmath because δ(σ,b)=. 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 S,I, and F now consist of all accessible states, and δ is just a restriction on the domain of δ, since if a state s is accessible, so is any state in δ(s,a) for any aΣ.

Again, referring the example above, A is deterministic, and it is equivalent to the following deterministic accessible automaton:

The languagePlanetmathPlanetmath accepted by the automaton is represented by the regular expressionMathworldPlanetmath a(ab)*.

Titlesimplified automaton
Canonical nameSimplifiedAutomaton
Date of creation2013-03-22 19:01:51
Last modified on2013-03-22 19:01:51
OwnerCWoo (3771)
Last modified byCWoo (3771)
Numerical id8
AuthorCWoo (3771)
Entry typeDefinition
Classificationmsc 03D05
Classificationmsc 68Q45
Synonymtrim automaton
Synonymcoaccessible
Related topicReducedAutomaton
Definesreachable
Definesaccessible
Defineslive
Definesuseful

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 8:18:44