Utknąłem, rozwiązując następne ćwiczenie:
Argumentuj, że jeśli jest bezkontekstowy i jest zatem regularny (tj. odpowiedni iloraz ) jest pozbawiony kontekstu.
Wiem, że powinien istnieć PDA, który akceptuje i DFA, który akceptuje . Próbuję teraz połączyć te automaty z PDA, który akceptuje odpowiedni iloraz. Jeśli potrafię zbudować, to to udowodniłemjest 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.
formal-languages
context-free
finite-automata
closure-properties
pushdown-automata
Dommicentl
źródło
źródło
Odpowiedzi:
Oto podpowiedź.
Potrzebujesz maszyny, aby początkowo zaakceptować część słowa odL , zużywając taśmę. Następnie, nie zużywając niczego, musisz znaleźć słowo odR któ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.
źródło
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 tow∈Σ∗ . 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.
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ćGL więc masz kontrolę nad przyrostkami; używając Postać normalna Chomsky'ego pomaga.
źródło
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:
Bardziej formalnie:
źródło