Wariant problemu po korespondencji

Jest to prawdopodobnie dość proste, ale weź pod uwagę standardowy problem z korespondencją:

Biorąc pod uwagę, i β 1 , ... , β N , znaleźć sekwencję indeksów i 1 , ... , i K tak, że a i 1 ⋯ α i K = β i 1 ⋯ β i K . Jest to oczywiście nierozstrzygalne.$\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}$

Teraz nazywam to „wariantem”, ale tak naprawdę nie jest - w gruncie rzeczy odrzuca „korespondencję”. W każdym razie rozważ następujący wariant:

Biorąc pod uwagę i β 1 , … , β N , znajdź dwie sekwencje wskaźników i 1 , … , i K , j 1 , … , j K takie, że α i 1 ⋯ α i K = β j 1 ⋯ beta J K . Co można powiedzieć o tym wariancie? Jeśli to trywialne, przepraszam!$\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}}$

Ta nowa wersja - gdzie - jest rozstrzygalna.$K = K'$

Pokażmy, że język to CFL. Wtedy rozstrzygalność wynika z rozstrzygalności pustki świetlówki kompaktowej.$L := \bigcup_{k \geq 1} (A^k \ \cap \ B^k)$

Będziemy projektować PDA przyjąć . Na wejściowego x , to PDA będzie próbował skonstruować dwa factorizations z X jedno używa słowa A , a inne przy użyciu słów pensjonatów . Użyje licznika na stosie, aby upewnić się, że te dwa czynniki są tej samej długości. Koncepcyjnie będę odnosił się do faktoryzacji A x siedzenia na szczycie x i faktoryzacji B jako siedzenia na dnie x . Wtedy stos będzie zawierał n liczników, jeśli bezwzględna wartość różnicy liczby słów dopasowanych u góry, minus liczba słów u dołu, wynosi$L$$x$$x$$A$$B$$A$$x$$x$$B$$x$$n$ . Potrzebujemy innego stanu PDA, aby zapisać, który odpowiedni znak odpowiada n (co mówi nam, czyfaktoryzacja A jest dłuższa niżfaktoryzacja B lub odwrotnie).$n$$n$$A$$B$

Jak skanować litery , my niedeterministycznie odgadnąć słowo t z A i słowo u z B do którego zaczyna ten list. Kiedy odgadnąć, jesteśmy zobowiązani do dopasowania resztę t oraz u przeciwko X ; jeśli w którymkolwiek momencie nasz mecz się nie powiedzie, zatrzymujemy się w tym niedeterministycznym wyborze. Więc my także utrzymać w stanie naszej PDA, przyrostek z T i U , który pozostaje do meczu.$x$$t$$A$$u$$B$$t$$u$$x$$t$$u$

Gdy skanujemy kolejne litery, kontynuujemy dopasowywanie, dopóki nie osiągniemy końca lub końca u (lub obu). Kiedy uderzamy w koniec słowa, odpowiednio aktualizujemy stos, a następnie odgadujemy nowe słowo, które będzie pasowało na górze lub na dole (lub obu).$t$$u$

Akceptujemy, jeśli przyrostki pozostałe do dopasowania są zarówno puste u góry, jak iu dołu, a stos nie zawiera liczników.

Możemy zbudować ten PDA skutecznie, abyśmy mogli skutecznie zdecydować, czy coś akceptuje, czy nie (na przykład, skutecznie przekształcając w gramatykę a następnie stosując zwykłą metodę, aby sprawdzić, czy G generuje cokolwiek).$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$