Gramatyka kontekstowa dla języka słów połączonych ze sobą

Szukam gramatyki kontekstowej opisującej następujący język: .$L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\}$

Mam problem z tym, że żadne reguły, takie jak są dozwolone i dlatego nie mogę umieścić żadnego nieterminala wskazującego „środek” słowa. Czy jest jakiś sposób na rozwiązanie tego problemu?$X \to \varepsilon$

Rzeczywiście istnieje prosta sztuczka, która pozwala dodać dodatkowe informacje w określonej pozycji: wystarczy zastąpić literę sąsiadującą z pozycją i oznaczyć ją informacją oraz oryginalną literą.

W twoim przykładzie, masz nieterminalny na środku, ale ponieważ nie można go usunąć, liczy się on również jako zwykła litera. Mamy więc dwie kopie i aby wskazać zastąpione litery. Pod koniec wyprowadzania znaczniki należy zastąpić ich literą, prostymi produkcjami, takimi jak .$M$$M_a$$M_b$$M_a\to a$

W większości przypadków zastosowanie należy wykonać na końcu procesu wyprowadzania. W niektórych konstrukcjach nie musi to być „mierzone”: gdy zniknie zbyt wcześnie, wyprowadzenie nie może znaleźć właściwej pozycji i proces nie zakończy się pomyślnie. W innych przypadkach potrzeba pewnego rodzaju kontroli. Czasami robi się to poprzez wprowadzenie nieterminala jako sygnału, który porusza się wzdłuż liter. Ponownie, ten sygnał powinien również przenosić terminal, w przeciwnym razie wpadniesz w te same problemy.$M_a\to a$$M$

Przenoszenie informacji wokół jest łatwy w tzw monotonicznych gramatyk ( z ) stosując zasady jak , które mogą być postrzegane jako skoków nad . Aby uzyskać prawidłową gramatykę kontekstową, należy podzielić ją na trzy etapy: . w każdej produkcji jedna litera jest zmieniana we właściwym kontekście. Potrzeba trochę wyobraźni, aby zobaczyć, że ten proces nie wchodzi w interakcje z innymi częściami wyprowadzania. Na przykład, co dzieje się, gdy w ostatnim etapie jest po raz pierwszy zaangażowany w inny etap wyprowadzania?$\alpha\to \beta$$|\alpha|\le\beta|$$XA \to AX$$X$$A$$XA \to XA^X, XA^X\to AA^X, AA^X\to AX$$A$

Może to nie działać w przypadku bardzo krótkich słów, gdy dostępnych jest więcej informacji niż dostępnych pozycji. Najprostszym rozwiązaniem tego jest zignorowanie krótkich ciągów w swojej konstrukcji i wygenerowanie ich osobno.

Krótka domyślna odpowiedź: wymyśl LBA, który akceptuje język i użyj symulacji użytej do udowodnienia, że ​​gramatyki kontekstowe i LBA definiują ten sam zestaw języków. Ale nie o to oczywiście chodzi.

W tym konkretnym przypadku spróbuj pomyśleć o użyciu gramatyki liniowo-prawej dla dwa razy, jeden dla lewej i jeden dla prawej połowy. Musisz tylko upewnić się, że obie gramatyki wyprowadzają „zsynchronizowane”.$\Sigma^*$

Można to zrobić, zamieniając token sterujący. Oznacza to, że lewe gramatyki wybierają regułę, generują odpowiedni żeton kontrolny i przekazują go do prawej gramatyki. Prawidłowa gramatyka widzi token kontrolny i wykonuje regułę dopasowania. Zauważ, że możesz w ten sposób zaimplementować dwukierunkową komunikację, ale tutaj nie jest to konieczne.

Jest jeden problem z gramatykami kontekstowymi: nigdy nie mogą usuwać terminali (z wyjątkiem jeśli puste słowo jest w języku). Dlatego musimy stworzyć tylko tyle terminali, ile będziemy potrzebować; żaden nie może być zbędny.$S \to \varepsilon$

Jednym ze sposobów na osiągnięcie tego jest użycie tej samej sztuczki, co w przypadku niektórych dowodów dotyczących LBA: wygeneruj wszystkie nieterminale, których będziesz najpierw potrzebować , tj. Przygotuj „taśmę”. Później „poruszaj się” po tej taśmie. Tylko „na końcu” zamień wszystkie nie-terminale na terminale.

Niech więc z (konstrukcja łatwo rozciąga się na większe alfabety) i , podane przez następujące reguły. to reguły generowania „taśmy”. Zauważ, że czapka oznacza „pozycję głowy”, a indeksy oznaczają, do której połowy słowa należy nieterminalny. Krótkie słowa są generowane, aby zabezpieczyć niektóre reguły poniżej. Teraz potrzebujemy reguł, aby uzyskać jeden symbol w lewej części:$G=(N, \Sigma, \delta, S)$$\Sigma = \{a,b\}$$N$$\delta$

$\qquad \begin{align} S &\to \hat{X}_l S' X_r \mid aaaa \mid abab \mid baba \mid bbbb \mid aa \mid bb \mid \varepsilon \\ S' &\to X_l S' X_r \mid X_l \hat{X}_r \end{align}$

$l,r$

$\qquad \begin{align} \hat{X}_l X_l &\to X_\gamma \hat{X}^\gamma_l \\ \hat{X}_l X_\alpha &\to X_\gamma X^\gamma_\alpha \end{align}$

dla wszystkich . Zwróć uwagę, jak używamy górnego indeksu do przenoszenia wygenerowanego symbolu w prawo. i są „końcowymi” nieterminalami, które będą używane tylko do przesuwania tokena sterującego i uzyskiwania terminali później. Zauważ ponadto, że druga reguła jest (tylko) używana dla ostatniego symbolu prawej połowy. Aby przenieść przeniesienie do prawej połowy, musimy przejść obok pozostałych i już wygenerowanych :$(\alpha, \gamma) \in \Sigma^2$$X_a$$X_b$

$X_l$$X_\alpha$

$\qquad \begin{align} \hat{X}^\gamma_l X_l &\to \hat{X}_l X^\gamma_l \\ \hat{X}^\gamma_l X_\alpha &\to \hat{X}_l X^\gamma_\alpha \\ X^\gamma_l X_l &\to X_l X^\gamma_l \\ X^\gamma_l X_\alpha &\to X_l X^\gamma_\alpha \\ X^\gamma_\alpha X_\beta &\to X_\alpha X^\gamma_\beta \end{align}$

dla wszystkich . Teraz, gdy carry osiągnie odpowiedni token kontrolny, musimy naśladować regułę zastosowaną po lewej stronie: dla wszystkich$(\alpha, \beta, \gamma) \in \Sigma^3$

$\qquad\begin{align} X^\gamma_l \hat{X}_r &\to X_l \hat{X}^\gamma_r \\ X^\gamma_\alpha \hat{X}_r &\to X_\alpha \hat{X}^\gamma_r \\ \hat{X}^\gamma_r X_r &\to X_\gamma \hat{X}_r \\ \hat{X}^\gamma_r &\to X_\gamma \end{align}$

$(\alpha, \gamma) \in \Sigma^2$. Zauważ, że pierwsza reguła jest używana dla pierwszego symbolu prawej połowy, i że ostatnia reguła może być użyta tylko dla ostatniego symbolu, w przeciwnym razie wyprowadzenie nigdy się nie kończy. Teraz potrzebujemy tylko reguł kończących dla wszystkich i gotowe. Te zasady również można zastosować dopiero po wykonaniu wszystkiego (po lewej), w przeciwnym razie wyprowadzenie nie zostanie zakończone. Zauważ, że ta gramatyka jest niejednoznaczna. Można nie tylko (bezpiecznie) zastosować dowolnym miejscu na lewo od lewej „głowy” w dowolnym momencie, ale może być jednocześnie prowadzonych wiele operacji przenoszenia. Ponieważ nigdy nie mogą się dogonić, utrzymywana jest poprawna kolejność.

$\qquad X_\alpha \to \alpha$

$\alpha \in \Sigma$

$X_\alpha \to \alpha$

Trzeba jeszcze jedna uwaga: powyżej gramatyki nie zależy od kontekstu, ponieważ wiele reguł zmienia oba symbole po lewej stronie. Nie jest to dozwolone w przypadku gramatyk kontekstowych. Na szczęście możemy symulować dowolną regułę w postaci przez więc jesteśmy dobrzy i możemy pracować z mniejszą gramatyką. Wykazanie, że interferencja między wieloma takimi symulacjami nie szkodzi, pozostawia się jako ćwiczenie.$R$

$\qquad A B \to C D$



$\qquad \begin{align} A B &\to A Y_R \\ A Y_R &\to X_R Y_R \\ X_R Y_R &\to X_R D \\ X_R D &\to C D \end{align}$

Czy widzisz, jak rozszerzyć to na ? Czy to działa również dla ? Czy możesz użyć tej samej konstrukcji dla dowolnego dla zwykłego ?$L_k = \{ w^k \mid w \in \Sigma^*\}$$L = \bigcup_{i\geq 1} L_k$$L^k$$L$

Chociaż nie wiem, jak będzie wyglądała gramatyka kontekstowa, możesz obejść swój problem z symbolem w następujący sposób.$X$

Wiesz, że twoje połączone słowa muszą mieć co najmniej długość . Dlatego możesz po prostu „zakodować” te zasady swojej gramatyki według kilku zasad, takich jak: $w$$|w| \ge 1$$\varepsilon$

Chociaż nie widzę jeszcze ogólnego rozwiązania, ponieważ moim zdaniem wydaje się, że twoje lewe strony reguł gramatycznych potencjalnie stają się arbitralnie długie, ponieważ myślę, że spróbowałbyś rozważyć prefiksy jakoś w swoich regułach.$w$