quotient automaton

A (nondeterministic) finite automaton is a quintuple A = ⟨Σ, S, s₀, δ, S_f⟩, where:

• Σ is the input alphabet (a finite, non-empty set of symbols),
• S is a finite, non-empty set of states,
• s₀ is the initial state, an element of S,
• δ is the state-transition relation: δ ⊆ S × Σ × S, and
• S_f is the set of final states, a (possibly empty) subset of S.{{cite book | isbn=0-201-02988-X | author1=John E. Hopcroft |author2= Jeffrey D. Ullman | author1-link=John E. Hopcroft |author2-link= Jeffrey D. Ullman |title=Introduction to Automata Theory, Languages, and Computation | location=Reading/MA | publisher=Addison-Wesley | year=1979 }}Hopcroft and Ullman (sect.2.3, p.20) use a slightly deviating definition of δ, viz. as a function from S × Σ to the power set of S.

A string a₁...a_n ∈ Σ^* is recognized by A if there exist states s₁, ..., s_n ∈ S such that ⟨s_i-1,a_i,s_i⟩ ∈ δ for i=1,...,n, and s_n ∈ S_f. The set of all strings recognized by A is called the language recognized by A; it is denoted as L(A).

For an equivalence relation ≈ on the set S of A’s states, the quotient automaton A/_≈ = ⟨Σ, S/_≈, [s₀], δ/_≈, S_f/_≈⟩ is defined by{{cite report | url=http://www.irisa.fr/vertecs/Publis/Ps/PI-1839.pdf | issn=1166-8687 | author=Tristan le Gall and Bertrand Jeannet | title=Analysis of Communicating Infinite State Machines Using Lattice Automata | institution=Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA) — Campus Universitaire de Beaulieu | type=Publication Interne | number=1839 | date=Mar 2007 }}{{rp|5}}

• the input alphabet Σ being the same as that of A,
• the state set S/_≈ being the set of all equivalence classes of states from S,
• the start state [s₀] being the equivalence class of A’s start state,
• the state-transition relation δ/_≈ being defined by δ/_≈([s],a,[t]) if δ(s,a,t) for some s ∈ [s] and t ∈ [t], and
• the set of final states S_f/_≈ being the set of all equivalence classes of final states from S_f.

The process of computing A/_≈ is also called factoring A by ≈.

For example, the automaton A shown in the first row of the tableIn the automaton diagrams in the table, {{color|#008000|symbols from the input alphabet}} and {{color|#800000|state names}} are colored in {{color|#008000|green}} and {{color|#800000|red}}, respectively; final states are drawn as double circles. is formally defined by

• Σ^A = {0,1},
• S^A = {a,b,c,d},
• s{{su|b=0|p=A}} = a,
• δ^A = { ⟨a,1,b⟩, ⟨b,0,c⟩, ⟨c,0,d⟩ }, and
• S{{su|b=f|p=A}} = { b,c,d }.

It recognizes the finite set of strings { 1, 10, 100 }; this set can also be denoted by the regular expression "1+10+100".

The relation (≈) = { ⟨a,a⟩, ⟨a,b⟩, ⟨b,a⟩, ⟨b,b⟩, ⟨c,c⟩, ⟨c,d⟩, ⟨d,c⟩, ⟨d,d⟩ }, more briefly denoted as a≈b,c≈d, is an equivalence relation on the set {a,b,c,d} of automaton A’s states.

Building the quotient of A by that relation results in automaton C in the third table row; it is formally defined by

• Σ^C = {0,1},
• S^C = {a,c},Strictly formal, the set is S^C = { [a], [b], [c], [d] } = { [a], [c] }. The class brackets are omitted for readability.
• s{{su|b=0|p=C}} = a,
• δ^C = { ⟨a,1,a⟩, ⟨a,0,c⟩, ⟨c,0,c⟩ }, and
• S{{su|b=f|p=C}} = { a,c }.

It recognizes the finite set of all strings composed of arbitrarily many 1s, followed by arbitrarily many 0s, i.e. { ε, 1, 10, 100, 1000, ..., 11, 110, 1100, 11000, ..., 111, ... }; this set can also be denoted by the regular expression "1^*0^*".

Informally, C can be thought of resulting from A by glueing state {{not a typo|a}} onto state b, and glueing state c onto state d.

The table shows some more quotient relations, such as B = A/_a≈b, and D = C/_a≈c.

• For every automaton A and every equivalence relation ≈ on its states set, L(A/_≈) is a superset of (or equal to) L(A).{{rp|6}}
• Given a finite automaton A over some alphabet Σ, an equivalence relation ≈ can be defined on Σ^* by x ≈ y if ∀ z ∈ Σ^*: xz ∈ L(A) ↔ yz ∈ L(A). By the Myhill–Nerode theorem, A/_≈ is a deterministic automaton that recognizes the same language as A.{{rp|65–66}} As a consequence, the quotient of A by every refinement of ≈ also recognizes the same language as A.

• Quotient group
• Quotient category

{{reflist|group=note}}

{{reflist}}

Category:Finite-state machines