Menor NFA aceitando concatenações de duas palavras do comprimento

Seja$k\in \mathbb N$

Estou procurando uma compilação NFA pequena para a linguagem de concatenação de duas palavras do comprimento que são diferentes em termos de índice, ou seja,$k$

Observe que, como é fixo, , e é regular como idioma finito.$k$$|L_k|=(|\Sigma|\cdot(|\Sigma|-1))^k$

$%$

O DFA trivial para o idioma contém estados +1 e apenas "lembra" quais letras foram exibidas durante as primeiras k letras; no entanto, se k = o (| \ Sigma |) , podemos criar um NFA significativamente menor.$k$$|\Sigma| \choose k$$+1$$k$$k=o(|\Sigma|)$

$%$

Um NFA "simples", pois seria do tamanho $O^*(2^{2k})$ (mais precisamente, $O(k^2 \log |\Sigma| 2^{2k+O(\log^2 k)})$ ):

$%$

1. Tome um conjunto universal (isto é, um conjunto de vetores modo que, para cada vetor e índices, existe um vetor tal que , ou seja, se olharmos apenas para esses índices em , encontraremos ). Tais famílias de tamanho são conhecidas.$(|\Sigma|,2k)$$\mathcal V\subseteq \{0,1\}^{|\Sigma|}$$u\in \{0,1\}^2k$$2k$$v\in \mathcal V$$v_{|I}=u$$k$$v$$u$$O^*(2^{2k})$

   Pensamos em cada vetor como uma função , onde .$v$$\Sigma\to \{0,1\}$$v(\sigma_i)=1⟺v_i=1$

$%$

1. Crie um NFA da seguinte maneira:

   1. A partir do estado inicial criar um -transition para um novo estado para qualquer . Denote esse estado por .$q_0$$\epsilon$$v\in \mathcal V$$q_v$

   2. A partir de cada construa um caminho de estados que aceite todas as palavras cujas primeiras letras sejam mapeadas por a 0 e as últimas letras serão mapeadas por a 1.$q_v$$k$$v$$k$$v$

$%$

Basicamente, a idéia é que o conjunto universal nos permita particionar as letras que podem aparecer nos primeiros símbolos do resto, e obtemos todas as palavras no idioma, pois deve haver um vetor correspondente que particiona corretamente.$k$$v\in \mathcal V$

Então, as perguntas são:

Qual é o tamanho do menor NFA para ?$L$

Essa construção é ideal?

Qual limite inferior podemos provar para esse tamanho de autômato?

Atualização: isso não responde à pergunta que o pôster original estava procurando e não ajuda no caso geral em que , portanto a pergunta permanece em aberto.$|\Sigma|>2$

Aqui está uma construção mais simples, mostrando que, no caso em que , declara suficiente, e na verdade você pode reconhecer o idioma com um DFA com esse muitos estados.$\Sigma=\{0,1\}$$O(k \cdot 2^{2k})$

Vamos começar analisando o idioma do complemento:

Observe que isso pode ser reconhecido por um NFA comestados. O NFA adivinha primeiro um símbolo , depois aceita todas as cadeias onde .$2k^2 |\Sigma|$$i$$x$$u \cdot v$$u_i = v_i = x$

Converta isso em um DFA usando a construção de subconjunto padrão. Obtemos um DFA com estados. Agora podemos calcular seu complemento, que é outro DFA com o mesmo número de estados que reconhece . Por ser um DFA, também é automaticamente um NFA.$\le 2^{|\Sigma| k + 1} k$$L_k$

Isso supera sua construção para o caso em que , mas, de outro modo, leva um NFA maior que o seu esquema. No entanto, pensei que poderia ser interessante, tanto porque é muito simples e porque na verdade fornece um DFA (não apenas um NFA) para reconhecer seu idioma .$|\Sigma|=2$$L_k$