Quotient automaton


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 finite automaton is a quintuple A = ⟨Σ, S, s0, δ, Sf⟩, where:
A string a1...an ∈ Σ* is recognized by A if there exist states s1,..., sn ∈ S such that ⟨si-1,ai,si⟩ ∈ δ for i=1,...,n, and sn ∈ Sf. The set of all strings recognized by A is called the language recognized by A; it is denoted as L.
For an equivalence relation ≈ on the set S of A’s states, the quotient automaton A/≈ = ⟨Σ, S/≈, , δ/≈, Sf/≈⟩ is defined by
The process of computing A/≈ is also called factoring A by ≈.

Example

Automaton
diagram		Recognized
language		Is the quotient of--
A byB byC by---
A:1+10+100
B:1*+1*0+1*00a≈b
C:1*0*a≈b, c≈dc≈d
D:*a≈b≈c≈da≈c≈da≈c

For example, the automaton A shown in the first row of the table is formally defined by
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
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