(N) DFA com o mesmo estado inicial / de aceitação

O que se sabe sobre a classe de idiomas reconhecida por autômatos finitos com o mesmo estado inicial e de aceitação? Este é um subconjunto adequado dos idiomas regulares (já que todos os idiomas contêm a string vazia), mas qual é a sua fraqueza? Existe uma caracterização algébrica simples?

O mesmo vale para idiomas reconhecidos por autômatos não determinísticos com o mesmo conjunto de estados inicial e de aceitação.

Esta questão é resolvida para autômatos determinísticos e para autômatos inequívocos no livro [1]

[1] J. Berstel, D. Perrin, C, Reutenauer, Codes and autômatos, vol. 129 da Enciclopédia de Matemática e suas Aplicações, Cambridge University Press, 2009.

No caso de autômatos determinísticos, a caracterização é dada na Proposição 3.2.5. Lembre-se que um submonoid de A * é unitária direito se, para todos u , v ∈ M , u , u v ∈ M implica v ∈ M . $M$$A^*$$u, v \in M$$u, uv \in M$$v \in M$

Proposição . Seja um subconjunto regular de A ∗ . As condições seguintes são equivalentes:$L$$A^*$

1. é um submonóide unitário direito,$L$
2. para algum código de prefixo P ,$L = P^*$$P$
3. O autômato mínimo de tem um estado final único, ou seja, o estado inicial.$L$
4. Existe um autômato determinístico que reconhece tendo o estado inicial como estado final único.$L$

Para autômatos inequívocos, a caracterização segue do Teorema 4.2.2 e pode ser declarada da seguinte maneira:

Proposição . Seja um subconjunto regular de A ∗ . As condições seguintes são equivalentes:$L$$A^*$

1. é um submonóide livre de A ∗ ,$L$$A^*$
2. para algum código C ,$L = C^*$$C$
3. Existe um autômato inequívoco que reconhece tendo o estado inicial como estado final único.$L$

Finalmente, para autômatos não determinísticos, a caracterização é simplesmente que é um submonóide de A ∗ .$L$$A^*$

Autômatos finitos nos quais o estado inicial também é o único estado de aceitação têm a forma , onde r é uma expressão regular. No entanto, como J.-E. Pin aponta abaixo, o inverso não é verdadeiro: existem idiomas no formato r ∗ que não são aceitos por um DFA com um estado de aceitação exclusivo.$r^∗$$r$$r^*$

Intuitivamente, dada uma sequência de estados modo que q 0 = q n ou n = 0 ou o diagrama de estados subjacente deve ter um ciclo envolvendo q 0 . O último caso é capturado algebricamente pela estrela Kleene.$q_0, \ldots, q_n$$q_0 = q_n$$n = 0$$q_0$

Uma subclasse importante dessa família é uma subclasse de linguagens reversíveis em 0. Um idioma é 0-reversível se a reversão do DFA mínimo para o idioma também for determinística. A operação de reversão é definida como a troca dos estados inicial e final e a inversão da relação de borda do DFA. Isso significa que um idioma reversível 0 pode ter apenas um estado de aceitação. Sua pergunta está adicionando uma restrição adicional de que esse estado deve ser o estado inicial. Sua restrição não define os idiomas reversíveis em 0 porque o DFA mínimo para esses idiomas pode ter estados iniciais e finais distintos.

A classe das línguas reversíveis é interessante porque foi uma das primeiras famílias de línguas com infinitas seqüências de caracteres que foi aprendida apenas com exemplos positivos. O trabalho de Angluin também fornece uma caracterização algébrica.

Inferência de línguas reversíveis , Dana Angluin, Jornal da ACM, 1982

Você pode se referir aos autômatos de semi-flores, como o artigo coloca: "Um autômato de semiflores (SFA) é um autômato de acabamento com um estado inicial único que é igual a um estado final único no qual todos os ciclos passam pelo estado final inicial ". Consulte "A DECOMPOSIÇÃO DA HOLONOMIA DOS AUTOMÁTICOS SEMI-FLORES CIRCULARES" - Shubh Narayan Singh, KV Krishna.