Autômatos que reconhecem

Seja um alfabeto finito. Um código sobre é um subconjunto de de tal modo que cada palavra em pode ser representada unicamente como uma concatenação de palavras . Um código $\Sigma$ $X$ $\Sigma$ $\Sigma^*$ $X^*$ $X$ $X$ éfinitose $|X|$ é finito. O que se sabe sobre autômatos (mínimos) que reconhecem $X^*$ para um código finito $X$ ? Existe alguma caracterização de tais autômatos (em termos da estrutura do autômato, sem conhecer $X$ )? É possível, com esse autômato, extrair o código $X$ em tempo polinomial?

Também estou interessado nessas perguntas quando omitimos o fato de que $X$ é um código, ou seja, supomos apenas que $X$ é um conjunto finito de palavras.

automata-theory Andrew Ryzhikov
fonte

O que você quer saber sobre esses autômatos? Parece fácil construir um DFA para

X^{*}

$X^*$ cujo tamanho pode ser facilmente caracterizado (é basicamente o número de prefixos exclusivos de strings em

X

$X$ e, portanto, é no máximo a soma dos comprimentos de palavras em

X

$X$ ; em particular, é tamanho polinomial). Dado esse DFA, também parece fácil extrair as palavras de código em

X

$X$ , enumerando todos os ciclos do nó inicial de volta para si mesmo. Quais são especificamente as suas perguntas? Que pensamento você já fez? Consulte a parte "As perguntas devem se basear em ..." da nossa Central de Ajuda .

@ DW, obviamente, nem todos os autômatos têm essa propriedade. Por isso, pergunto se existe uma caracterização (esperançosamente polinomial) de tais autômatos. Além disso, não vejo como extrair o

enumerando todos os ciclos do estado inicial para ele mesmo. De fato, pode haver um número infinito de ciclos, pois não podemos restringir apenas a ciclos sem auto-interseções. Você pode por gentileza ser mais específico?

X

$X$

Andrew Ryzhikov

Se bem entendi, você perguntou sobre autômatos mínimos. Eu acho que todos os DFAs mínimos serão isomórficos ao que eu descrevi. Se você está perguntando sobre todos os autômatos, não necessariamente mínimos, sugiro que você edite a pergunta para esclarecer. Não entendo por que você não pode se restringir apenas a ciclos sem auto-interseções; a propriedade livre de prefixo significa que é seguro fazê-lo, e se

for finito, haverá apenas muitos desses ciclos finitos. Sugiro que você pense sobre o problema por um tempo e depois edite a pergunta para compartilhar todos os resultados que conseguiu até agora.

X

$X$

Essa pergunta não é a mesma que a primeira versão do cstheory.stackexchange.com/questions/4284/… , onde

podem diferir, exceto que você também solicita o tempo de execução?

K

$K$

K^{'}

$K'$

Domotorp 16/04

@domotorp Você está certo, verificando se um conjunto de palavras é um código em tempo polinomial e é um fato bem conhecido (consulte ex. www-igm.univ-mlv.fr/~berstel/LivreCodes/ Codes.html , subseção 0.4). O que eu quero é que, tendo apenas um autômato mínimo reconhecendo algo, verifique se esse algo é uma estrela de um código.

Andrew Ryzhikov

Respostas:

Como essa pergunta não recebeu resposta por um longo tempo, deixe-me oferecer uma resposta parcial para a primeira parte da pergunta:

O que se sabe sobre autômatos (mínimos) que reconhecem para um código finito ? $X^∗$ $X$

Dado um conjunto finito de palavras , o autômato flor de é o autômato finito não determinístico , onde , $X$ $X^*$ $\mathcal{A} = (Q, A, E, I, F)$ $Q = \{1, 1\} \cup \{ (u, v) \in A^+ \times A^+ \mid uv \in X \}$ , com quatro tipos de transições: $I = F = \{(1,1)\}$ É fácil ver que esse autômato reconhece. Por exemplo, see, o autômato de flores deé o seguinte

\begin{aligned} (você, uma v) & \overset{uma}{⟶} (você uma, v) de tal modo que você uma v \in X, (você, v) \neq (1 1, 1 1) \\ (você, uma) & \overset{uma}{⟶} (1 1, 1 1) de tal modo que você uma \in X, você \neq 1 1 \\ (1 1, 1 1) & \overset{uma}{⟶} (uma, v) de tal modo que uma v \in X, v \neq 1 1 \\ (1 1, 1 1) & \overset{uma}{⟶} (1 1, 1 1) de tal modo que uma \in X} \end{aligned}

$\begin{align*} (u, av) &\enspace{\buildrel{a} \over\longrightarrow}\enspace (ua, v) \text{ such that } uav \in X,\ (u, v) \neq (1,1) \\ (u, a) &\enspace{\buildrel{a} \over\longrightarrow}\enspace (1, 1) \text{ such that } ua \in X,\ u \neq 1 \\ (1, 1) &\enspace{\buildrel{a} \over\longrightarrow}\enspace(a, v) \text{ such that } av \in X,\ v \neq 1\\ (1, 1) &\enspace{\buildrel{a} \over\longrightarrow}\enspace (1, 1) \text{ such that } a \in X \bigr\} \end{align*}$

X^{*}

$X^*$

A = {a, b}

$A= \{a, b\}$

X = {a, b a, a a b, a b a}

$X = \{a, ba, aab, aba\}$

X^{*}

$X^*$

$\qquad\qquad\qquad$

Lembre-se que um autômato é inequívoca , se, dada dois estados e e uma palavra , existe no máximo um caminho de para com etiqueta . Em seguida, o seguinte resultado é válido: $p$ $q$ $w$ $p$ $q$ $w$

Teorema [1, Thm 4.2.2]. O conjunto é um código se o autômato de flores de não for ambíguo. $X$ $X^*$

O autômato de flores também possui uma propriedade algébrica que o torna relativamente próximo do autômato mínimo. Essa propriedade é válida para qualquer conjunto finito , mas é mais fácil declarar se livrando da palavra vazia, ou seja, considerando um idioma como um subconjunto de vez de . $X$ $A^+$ $A^*$

Lembre-se de que um semigrupo finito é localmente trivial se, para cada idempotente , . Um morfismo é localmente trivial se, para todo idempotente em , o semigrupo for localmente trivial. $R$ $e \in R$ $eRe = \{e\}$ $\pi:R \to S$ $e$ $S$ $\pi^{-1}(e)$

O semigrupo de transição do autômato de flores de é chamado de semigrupo de flores de . Como reconhece , existe um morfismo adjetivo de no semigrupo sintático de . $T$ $X^+$ $X^+$ $T$ $L^+$ $\pi$ $T$ $S$ $X^+$

Teorema . O morfismo é localmente trivial. $\pi:T \to S$

Uma conseqüência importante desse resultado é que o semigrupo de flores e o semigrupo sintático têm o mesmo número de classes regulares . $\mathcal{J}$

Referências

[ 1 ] J. Berstel, D. Perrin, C. Reutenauer, Codes and Automata . Encyclopedia of Mathematics and its Applications, 129. Cambridge University Press, Cambridge, 2010. xiv + 619 pp. ISBN: 978-0-521-88831-8

J.-E. PIN
fonte