Gdyby

9

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

Argumentuj, że jeśli L jest bezkontekstowy i R jest zatem regularny L/R={wxRs.twxL}(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łemL/Rjest 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.

Dommicentl
źródło
Witamy! Gdzie dokładnie utknąłeś, jakie jest twoje podejście?
Raphael
1
Wskazówka: zastanów się, jak najlepiej wykorzystać niedeterminizm.
Artem Kaznatcheev
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 naprawić formalnie.
Dommicentl
3
Skopiowałem twój komentarz do pytania. To lepsze miejsce na to.
Dave Clarke

Odpowiedzi:

8

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 odRktóre popchną maszynę do ostatecznego stanu. Wybrane słowo odR 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.

Dave Clarke
źródło
6

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 wL które mają przyrostek z R! To znaczy na poziomie intuicyjnym.

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

Pozwolić AL i AR PDA dla L i NFA dla Rodpowiednio. Zbuduj automatAnastępująco. Na wejściuwΣ, symulować AL. Pow jest zużywany, przejdź do zmodyfikowanego skrzyżowania AL,R z AL i AR, powstrzymując stan od AL. 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 AL,R osiągnąć jednocześnie stan końcowy, czyli jeśli w ma kontynuację x po to aby wxL i xR.

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ćGLwięc masz kontrolę nad przyrostkami; używając Postać normalna Chomsky'ego pomaga.

Załóżmy oba GL i GRsą podane w normalnej formie Chomsky'ego. ModyfikowaćGLtak, ż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ę wywodziGL i GRrównolegle (nieterminale są parami nieterminali); jeśli obie gramatyki zgadzają się na symbol terminala, usuń złożony nieterminal. W ten sposób przyrostekGL jest usuwany tylko wtedy, gdy można go uzyskać w GL i w GR, pozostaje wL/R.

Raphael
źródło
Pamiętaj, że nawet to, co znajduje się w obszarach spoilerów, nie jest ani rygorystyczne, ani formalne. Daj mi znać, jeśli potrzebujesz więcej szczegółów (po samodzielnym wypróbowaniu).
Raphael
6

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ć LAbyć językiem. Chcemy przeczytać słowow, ale zapytaj L czy wxjest w języku Więc chcemy stworzyć nowy język zL który ma x"wymazany". Możemy to zrobić za pomocą homomorfizmu, ale mogłoby to usunąć literyw. Rozwiązanie: podziel alfabet na dwa i użyj różnych liter dlaw i x.

Bardziej formalnie:

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

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).

sdcvvc
źródło
1
Jeśli chodzi o to, co jest warte, konstrukcja automatów skaluje się również do innych klas: w żadnym momencie tak naprawdę tego nie używamy ALjest PDA.
Raphael
Słuszna uwaga.
sdcvvc
1
Technicznie taka klasa (gdzie działa ten dowód) nazywa się stożkiem lub pełnym trio .
Hendrik Jan