En informática , en particular en la teoría del lenguaje formal , se puede obtener un autómata cociente a partir de un autómata finito no determinista dado uniendo algunos de sus estados. El cociente reconoce un superconjunto del autómata dado; en algunos casos, manejados por el teorema de Myhill-Nerode , ambos lenguajes son iguales.
Una cuerda a 1 ... a n ∈ Σ * es reconocida por A si existen estados s 1 , ..., s n ∈ S tales que ⟨ s i -1 , a i , s i ⟩ ∈ δ for i = 1,..., norte y s norte ∈ S f . El conjunto de todas las cadenas reconocidas por A se denomina lenguaje reconocido por A; se denota como L ( A ).
Para una relación de equivalencia ≈ sobre el conjunto S de estados de A , el cociente autómata A / ≈ = ⟨ Σ , S / ≈ , [ s 0 ], δ / ≈ , S f / ≈ ⟩ está definido por [2] : 5
Reconoce el conjunto finito de cadenas { 1, 10, 100 }; este conjunto también se puede denotar mediante la expresión regular "1+10+100".
La relación (≈) = { ⟨a,a⟩, ⟨a,b⟩, ⟨b,a⟩, ⟨b,b⟩, ⟨c,c⟩, ⟨c,d⟩, ⟨d,c⟩, ⟨ d,d⟩ }, denotado más brevemente como a≈b,c≈d, es una relación de equivalencia en el conjunto {a,b,c,d} de los estados del autómata A. Construir el cociente de A por esa relación da como resultado el autómata C en la tercera fila de la tabla; se define formalmente por
Reconoce el conjunto finito de todas las cadenas compuestas de arbitrariamente muchos 1, seguidos arbitrariamente de muchos 0, es decir, { ε, 1, 10, 100, 1000, ..., 11, 110, 1100, 11000, ..., 111, ... }; este conjunto también se puede denotar mediante la expresión regular "1 * 0 * ". De manera informal, se puede pensar que C es el resultado de A pegando el estado a al estado b, y pegando el estado c al estado d.