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 (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''.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
* 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

For example, the automaton A shown in the first row of the tableIn the automaton diagrams in the table, and are colored in and , respectively; final states are drawn as double circles. 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 = ,Strictly formal, the set is ''S''^C = = . The class brackets are omitted for readability.
* ''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'').
* 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''. 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

References

{{reflist

Finite-state machines