Autómata de cociente

En informática , y en particular en la teoría de lenguajes formales , se puede obtener un autómata cociente a partir de un autómata finito no determinista dado , combinando algunos de sus estados. El cociente reconoce un superconjunto del autómata original; en algunos casos, según el teorema de Myhill-Nerode , ambos lenguajes son iguales.

Un autómata finito (no determinista) es una quíntupla A = ⟨ Σ , S , s ₀ , δ , S _f ⟩, donde:

• Σ es el alfabeto de entrada (un conjunto finito y no vacío de símbolos),
• S es un conjunto finito y no vacío de estados,
• s ₀ es el estado inicial, un elemento de S ,
• δ es la relación estado-transición : δ ⊆ S × Σ × S , y
• S _f es el conjunto de estados finales, un subconjunto (posiblemente vacío) de S . ^{[ 1 ] [ nota 1 ]}

Una cadena a ₁ ... a _n ∈ Σ ^* es reconocida por A si existen estados s ₁ , ..., s _n ∈ S tales que ⟨ s _{i -1} , a _i , s _i ⟩ ∈ δ para i =1,..., n , y s _n ∈ S _f . El conjunto de todas las cadenas reconocidas por A se llama el lenguaje reconocido por A ; se denota como L ( A ).

Para una relación de equivalencia ≈ en el conjunto S de estados de A , el autómata cociente A / _≈ = ⟨ Σ , S / _≈ , [ s ₀ ], δ / _≈ , S _f / _≈ ⟩ se define por ^{[ 2 ] : 5}

• siendo el alfabeto de entrada Σ el mismo que el de A ,
• el conjunto de estados S / _≈ siendo el conjunto de todas las clases de equivalencia de estados de S ,
• el estado inicial [ s ₀ ] es la clase de equivalencia del estado inicial de A ,
• la relación de transición de estado δ / _≈ se define por δ / _≈ ([ s ], a ,[ t ]) si δ ( s , a , t ) para algún s ∈ [ s ] y t ∈ [ t ], y
• el conjunto de estados finales S _f / _≈ siendo el conjunto de todas las clases de equivalencia de estados finales de S _f .

El proceso de calcular A / _≈ también se denomina factorizar A por ≈.

Por ejemplo, el autómata A que se muestra en la primera fila de la tabla ^{[ nota 2 ]} se define formalmente por

• Σ ^A = {0,1},
• S ^A = {a,b,c,d},
• s ^A ₀ = a,
• δ ^A = { ⟨a,1,b⟩, ⟨b,0,c⟩, ⟨c,0,d⟩ }, y
• S ^A _f = { b,c,d }.

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⟩ }, denotada más brevemente como a≈b,c≈d, es una relación de equivalencia en el conjunto {a,b,c,d} de estados del autómata A. Construir el cociente de A mediante esa relación da como resultado el autómata C en la tercera fila de la tabla; se define formalmente por

• Σ ^C = {0,1},
• S ^C = {a,c}, ^{[ nota 3 ]}
• s ^C ₀ = a,
• δ ^C = { ⟨a,1,a⟩, ⟨a,0,c⟩, ⟨c,0,c⟩ }, y
• S ^C _f = { a,c }.

Reconoce el conjunto finito de todas las cadenas compuestas por un número arbitrario de 1s, seguidos de un número arbitrario de 0s, es decir { ε, 1, 10, 100, 1000, ..., 11, 110, 1100, 11000, ..., 111, ... }; este conjunto también puede denotarse mediante la expresión regular "1 ^* 0 ^* ". De manera informal, se puede pensar que C resulta de A al pegar el estado a sobre el estado b, y el estado c sobre el estado d.

La tabla muestra algunas relaciones de cociente más, como B = A / _a≈b y D = C / _a≈c .

• Para cada autómata A y cada relación de equivalencia ≈ en su conjunto de estados, L ( A / _≈ ) es un superconjunto de (o igual a) L ( A ). ^{[ 2 ] : 6}
• Dado un autómata finito A sobre algún alfabeto Σ , se puede definir una relación de equivalencia ≈ en Σ ^* mediante x ≈ y si ∀ z ∈ Σ * ^: xz ∈ L ( A ) ↔ yz ∈ L ( A ). Por el teorema de Myhill-Nerode , A / _≈ es un autómata determinista que reconoce el mismo lenguaje que A. ^{[ 1 ] : 65–66} Como consecuencia, el cociente de A por cada refinamiento de ≈ también reconoce el mismo lenguaje que A.

• Grupo de cocientes
• Categoría de cociente