Gdyby

Utknąłem, rozwiązując następne ćwiczenie:

Argumentuj, że jeśli $L$ jest bezkontekstowy i $R$ jest zatem regularny $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\}$(tj. odpowiedni iloraz ) jest pozbawiony kontekstu.

Wiem, że powinien istnieć PDA, który akceptuje $L$ i DFA, który akceptuje $R$. Próbuję teraz połączyć te automaty z PDA, który akceptuje odpowiedni iloraz. Jeśli potrafię zbudować, to to udowodniłem$L/R$jest bezkontekstowy. Ale utknąłem budując ten PDA.

Oto jak daleko doszedłem:

W połączonym PDA stany są kartezjańskim produktem stanów oddzielnych automatów. A krawędzie są krawędziami DFA, ale tylko te, dla których w przyszłości można osiągnąć końcowy stan pierwotnego PDA L. Ale nie wiem, jak to zapisać formalnie.

Oto podpowiedź.

Potrzebujesz maszyny, aby początkowo zaakceptować część słowa od $L$, zużywając taśmę. Następnie, nie zużywając niczego, musisz znaleźć słowo od$R$które popchną maszynę do ostatecznego stanu. Wybrane słowo od$R$ odgrywa rolę słowa wejściowego dla drugiej połowy obliczeń.

Oczywiście, rolę będzie odgrywać niedeterminizm, podobnie jak iloczyn między dwiema maszynami. Sztuką w sformalizowaniu tego jest dostosowanie produktu do radzenia sobie z faktem, że dane wejściowe pochodzą$R$ nie z wejścia.

Nie jestem pewien, do czego zmierzasz z kartezjańskim produktem; to symuluje oba automaty równolegle, co da ci skrzyżowanie. Ale chcesz, aby identyfikował wszystkie słowa w$L$ które mają przyrostek z $R$! To znaczy na poziomie intuicyjnym.

Załóżmy, że nasz wkład to $w \in \Sigma^*$. Oczywiście nie możemy sprawdzić wszystkich możliwych kontynuacji (dla członkostwa w$R$), ale tylko ich skończona liczba. Komentarz Artema jest tu najbardziej pomocny; możemy odgadnąć co przyrostek$x$ będzie i uruchomi na nim oba automaty.

Pozwolić $A_L$ i $A_R$ PDA dla $L$ i NFA dla $R$odpowiednio. Zbuduj automat$A$następująco. Na wejściu$w \in \Sigma^*$, symulować $A_L$. Po$w$ jest zużywany, przejdź do zmodyfikowanego skrzyżowania $A_{L,R}$ z $A_L$ i $A_R$, powstrzymując stan od $A_L$. Teraz zdecyduj dla każdego przejścia niedeterministycznie, który symbol jest następny na wirtualnym wejściu. Zaakceptować$w$ wtedy i tylko wtedy, gdy oba składniki $A_{L,R}$ osiągnąć jednocześnie stan końcowy, czyli jeśli $w$ ma kontynuację $x$ po to aby $wx \in L$ i $x \in R$.

Możesz także używać gramatyki formalnej. Czy widzisz, jak możesz wyprowadzić równolegle dwie gramatyki? Zasadniczo nie jest jasne, jak się dostosować$G_L$więc masz kontrolę nad przyrostkami; używając Postać normalna Chomsky'ego pomaga.

Załóżmy oba $G_L$ i $G_R$są podane w normalnej formie Chomsky'ego. Modyfikować$G_L$tak, że najbardziej prawy nie-terminalny jest rozróżnialny i czyni swój symbol początkowy nowym symbolem początkowym. Wprowadź do wyróżnionych wersji nieterminali nowe reguły, które prowadzą do gramatyki, która się wywodzi$G_L$ i $G_R$równolegle (nieterminale są parami nieterminali); jeśli obie gramatyki zgadzają się na symbol terminala, usuń złożony nieterminal. W ten sposób przyrostek$G_L$ jest usuwany tylko wtedy, gdy można go uzyskać w $G_L$ i w $G_R$, pozostaje $w \in L/R$.

Polecam użyć odpowiedzi Raphaela, która jest znacznie łatwiejsza do zrozumienia, ale tutaj jest alternatywa, używając właściwości zamknięcia zamiast automatów:

Pozwolić $L \subseteq A^{\ast}$być językiem. Chcemy przeczytać słowo$w$, ale zapytaj $L$ czy $w x$jest w języku Więc chcemy stworzyć nowy język z$L$ który ma $x$"wymazany". Możemy to zrobić za pomocą homomorfizmu, ale mogłoby to usunąć litery$w$. Rozwiązanie: podziel alfabet na dwa i użyj różnych liter dla$w$ i $x$.

Bardziej formalnie:

1) Utwórz $L' \subseteq (A \times \{0,1\})^{\ast}$ słów od $L$, z każdą literą oznaczoną 0 lub 1.
2) Przecinaj ją zwykłym językiem$(A \times {0})^{\ast} (R \times 1)$. Wymusza to, że wszystkie zera występują przed wszystkimi zerem, a druga część pochodzi$R$. Dokładne znaczenie$\times$pozostaje dla czytelnika.
3) Zastępstwo$(a,0) \to a$ i $(a,1) \to \varepsilon$.

Zastosowane właściwości zamknięcia: obraz homomorficzny, preimage, przecięcie z normalnymi językami. Zaleta: Ten dowód działa dla innych rodzin (na przykład zamień bezkontekstowo na zwykły).