Variante de problema de correspondência posterior

Provavelmente, isso é bem simples, mas considere o problema padrão de correspondência posterior:

Dado e β 1 , ... , β N , encontrar uma sequência de índices i 1 , ... , i K de tal modo que ácido a i 1 ⋯ α i K = β i 1 ⋯ β i K . Isso é, obviamente, indecidível.$\alpha_1, \ldots, \alpha_N$$\beta_1, \ldots, \beta_N$$i_1, \ldots, i_K$$\alpha_{i_1}\cdots \alpha_{i_K} = \beta_{i_1}\cdots \beta_{i_K}$

Agora, chamo isso de 'variante', mas não é realmente - essencialmente joga fora 'correspondência'. De qualquer forma, considere a seguinte variante:

Dado e β 1 , … , β N , encontre duas seqüências de índices i 1 , … , i K , j 1 , … , j K de modo que α i 1 ⋯ α i K = β j 1 ⋯ p j K . O que pode ser dito sobre essa variante? Se isso é trivial, minhas desculpas!$\alpha_1, \ldots, \alpha_N$$\beta_1, \ldots, \beta_N$$i_1, \ldots, i_K, j_1, \ldots, j_{K}$$\alpha_{i_1}\cdots \alpha_{i_K} = \beta_{j_1}\cdots \beta_{j_{K}}$

Esta nova versão - onde - é decidível.$K = K'$

Vamos mostrar que o idioma é uma CFL. Então, a decidibilidade decorre da decidibilidade do vazio de uma CFL.$L := \bigcup_{k \geq 1} (A^k \ \cap \ B^k)$

Vamos projetar um PDA para aceitar . Na entrada x , esta PDA tentará construir dois factorizações de x , um usando palavras de A , e os outros que usam palavras de B . Ele usará um contador na pilha para garantir que essas duas fatorações tenham o mesmo comprimento. Conceitualmente, vou me referir à fatoração A de x , na medida em que está sentado em cima de x, e à fatoração B, como na parte inferior de x . Então a pilha conterá n contadores se o valor absoluto da diferença do número de palavras correspondidas na parte superior, menos o número de palavras na parte inferior, for$L$$x$$x$$A$$B$$A$$x$$x$$B$$x$$n$ . Precisamos de outro estado do PDA para registrar qual o sinal apropriado corresponde a n (o que nos diz se afatoração A é maior que afatoração B ou vice-versa).$n$$n$$A$$B$

$x$$t$$A$$u$$B$$t$$u$$x$$t$$u$

$t$$u$

Aceitamos se os sufixos restantes a serem correspondidos estão vazios na parte superior e inferior e a pilha não contém contadores.

$G$

$k$$2^{O(l^2)}$$l$$A$$B$

$A$$B$$A$$B$

$\alpha_{i_1} \cdots \alpha_{i_K} = \beta_{j_1} \cdots \beta_{j_{K'}}$$K = K'$

$A$$\alpha_{i_1} \cdots \alpha_{i_K}$$B$$\beta_{j_1} \cdots \beta_{j_{K'}}$$A \cap B$$A,B$