Konstruujesz wszystkie języki bezkontekstowe z zestawu języków podstawowych i właściwości zamknięcia?

Jednym ze sposobów patrzenia na wyrażenia regularne jest konstruktywny dowód na następujący fakt: możliwe jest zbudowanie języków regularnych, zaczynając od małego zestawu języków i łącząc je za pomocą małego, stałego zestawu właściwości zamknięcia. W szczególności, jeśli zaczniemy od pustego języka, języka zawierającego pusty ciąg i języków wszystkich ciągów jednoznakowych, możemy zebrać wszystkie możliwe zwykłe języki przy użyciu unii, konkatenacji i gwiazdy Kleene.

Czy istnieje zestaw podstawowych języków i właściwości zamykania, których można użyć do wygenerowania wszystkich i tylko języków bezkontekstowych? (Aby wyjaśnić: nie pytam, czy można pisać wyrażenia regularne dla wszystkich CFL, co, jak wiem, jest niemożliwe. Zamiast tego zastanawiam się, czy istnieje sposób zaprojektowania struktury podobnej do wyrażenia regularnego dla CFL na podstawie te same podstawowe zasady).

Jest to możliwe, ale może nie dokładnie tak, jak pytasz. Na początek weź język Dyck wszystkich ciągów pasujących nawiasów przez dwie pary nawiasów, powiedz lub bardziej abstrakcyjnie .$D_2$$\{ [,], (,) \}$$a_1,b_1,a_2,b_2$

Następnie każdy język bezkontekstowy można uzyskać z przy użyciu homomorfizmów, homomorfizmów odwrotnych i przecięcia z normalnymi językami. Języki bezkontekstowe nazywane są „głównym stożkiem generowanym przez ”, w starych książkach oznaczono . Zobacz powiązane pytanie: „ Jakie języki są rozpoznawane przez maszyny z jednym licznikiem? ”$D_2$$D_2$$\mathcal{M}(D_2)$

W rzeczywistości potrzebujemy tylko jednej z każdej operacji (dobrze dobranej). Każdy CFL można zapisać , gdzie , są homomorfizmami, a jest językiem regularnym. Intuicyjnie, jest programem PDA, mapuje każdą instrukcję na odczytaną literę, na operacje push i pop stosu. Wreszcie koduje prawidłowe zachowanie stosu.$g(h^{-1}(D_2) \cap R)$$g$$h$$R$$R$$g$$h$$D_2$

Wynik ten jest związany z twierdzeniem Chomsky'ego-Schützenbergera (lub, jak widać na wikipedii, jednym z nich). Oświadczenie połączone tutaj w Wikipedii (a) nie wymaga odwrotnego homomorfizmu, podczas gdy (b) nie ogranicza się do dwóch par nawiasów. Twierdzenia tego typu pochodzą z obszaru „Abstrakcyjnych rodzin automatów”, gdzie Ginsburg i Greibach są ważnymi nazwami. Podobny wynik Nivata stwierdza, że ​​operacje w postaci dla stałych są transdukcjami stanu skończonego.$L \mapsto g(h^{-1}(L) \cap R)$$g,h,R$