Quotient automaton explained

In computer science, in particular in formal language theory, a quotient automaton can be obtained from a given nondeterministic finite automaton by joining some of its states. The quotient recognizes a superset of the given automaton; in some cases, handled by the Myhill–Nerode theorem, both languages are equal.

Formal definition

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.^{[1] [2]}

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^[3]

• 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 ≈.

Example

Quotient examples

ROWSPAN=2		ROWSPAN=2	Automaton diagram	ROWSPAN=2	Recognized language	COLSPAN=3	Is the quotient of
A by	B by	C by
A:		1+10+100
B:		1^*+1^*0+1^*00	a≈b
C:		1^*0^*	a≈b, c≈d	c≈d
D:		(0+1)^*	a≈b≈c≈d	a≈c≈d	a≈c

For example, the automaton A shown in the first row of the table^[4] is formally defined by

• Σ^A =,
• S^A =,
• s = a,
• δ^A =, and
• S = .

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

The relation (≈) =, more briefly denoted as a≈b,c≈d, is an equivalence relation on the set 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 =,
• S^C =,^[5]
• s = a,
• δ^C =, and
• S = .

It recognizes the finite set of all strings composed of arbitrarily many 1s, followed by arbitrarily many 0s, i.e. ; this set can also be denoted by the regular expression "1^*0^*".Informally, C can be thought of resulting from A by glueing state 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.

Properties

• For every automaton A and every equivalence relation ≈ on its states set, L(A/_≈) is a superset of (or equal to) L(A).^[3]
• 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.^[1] As a consequence, the quotient of A by every refinement of ≈ also recognizes the same language as A.

See also

• Quotient group
• Quotient category

Notes and References

1. Book: 0-201-02988-X . John E. Hopcroft . Jeffrey D. Ullman . John E. Hopcroft . Jeffrey D. Ullman . . Reading/MA . Addison-Wesley . 1979 .
2. 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.
3. Analysis of Communicating Infinite State Machines Using Lattice Automata . 1166-8687 . Tristan le Gall and Bertrand Jeannet . Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA) - Campus Universitaire de Beaulieu . Publication Interne . 1839 . Mar 2007 .
4. In the automaton diagrams in the table, and are colored in and, respectively; final states are drawn as double circles.
5. Strictly formal, the set is S^C = = . The class brackets are omitted for readability.