Czy hierarchia Chomsky'ego jest przestarzała?

45

Hierarchia Chomsky'ego (–Schützenberger) jest używana w podręcznikach teoretycznej informatyki, ale oczywiście obejmuje tylko bardzo niewielką część języków formalnych (REG, CFL, CSL, RE) w porównaniu z pełnym diagramem złożoności Zoo . Czy hierarchia odgrywa już jakąkolwiek rolę w bieżących badaniach? Znalazłem niewiele odniesień do Chomsky'ego tutaj na cstheory.stackexchange, aw Zoo Złożoności w ogóle nie wymieniono nazw Chomsky i Schützenberger.

Czy obecne badania bardziej koncentrują się na innych sposobach opisu, ale na gramatyce formalnej? Szukałem praktycznych metod opisywania języków formalnych z różną ekspresyjnością i natknąłem się na rosnący język kontekstowy (GCSL) i języki wyraźnie widoczne (VPL), które leżą między klasycznymi językami Chomsky'ego. Czy nie należy aktualizować hierarchii Chomsky'ego, aby ją uwzględnić? A może nie ma sensu wybierać konkretnej hierarchii z pełnego zestawu klas złożoności? O ile rozumiem, próbowałem wybrać tylko te języki, które mogą się zmieścić w lukach hierarchii Chomsky'ego:

REG (= Chomsky 3) ⊊ VPL ⊊ DCFL ⊊ CFL (= Chomsky 2) ⊊ GCSL ⊊ CSL (= Chomsky 1) ⊊ R ⊊ RE

Nadal nie rozumiem, gdzie mieszczą się „języki lekko kontekstowe” i „języki indeksowane” (gdzieś pomiędzy CFL i CSL), chociaż wydaje się, że ma to praktyczne znaczenie dla przetwarzania języka naturalnego (ale może coś praktycznego jest mniej interesujące w badaniach teoretycznych ;-). Ponadto możesz wspomnieć o GCSL ⊊ P ⊂ NP ⊂ PSPACE i CSL ⊊ PSPACE ⊊ R, aby pokazać związek ze znanymi klasami P i NP.

Znalazłem na GCSL i VPL:

Byłbym również szczęśliwy, jeśli znasz jakiś najnowszy podręcznik gramatyki formalnej, który dotyczy również VPL, DCLF, GCSL i gramatyki indeksowanej, najlepiej ze wskazówkami niż praktyczne zastosowania.

cc.complexity-theory automata-theory fl.formal-languages big-picture teaching Jakob
źródło
7
Drobna uwaga: nie widzę braku nazwisk Chomsky i Schützenberger w Zoo Złożoności jako dowodu, że „hierarchia Chomsky'ego jest przestarzała”. Hierarchia Chomsky'ego jest pojęciem w formalnej teorii języka. Zoo Złożoność to strona internetowa poświęcona głównie teorii złożoności, chociaż zawiera pewne pojęcia z formalnej teorii języków, takie jak języki bezkontekstowe. Są to powiązane, ale odrębne pola. Byłoby przestarzałe, gdyby nie zostało wspomniane w podręczniku formalnej teorii języka, ale nie wiem, czy tak jest.
Tsuyoshi Ito,
7
Dobra uwaga, Tsuyoshi. Szczerze mówiąc, chciałbym zobaczyć „zoo języków formalnych” z dobrym uzasadnieniem teoretycznym (odniesienia do prac naukowych!), Ale także praktycznymi zasobami. Na przykład istnieją dziesiątki wariantów składni Backus-Naur-Form i warianty wyrażeń regularnych (niektóre nawet nieregularne). Oprócz prostej hierarchii Chomsky'ego trudno mi było uzyskać jasny obraz aktualnego stanu badań w językach formalnych.
Jakob
Możesz także dodawać języki bez gwiazdek ściśle poniżej zwykłych języków. Są jak zwykłe, ale bez gwiazdy Kleene. Dobrze znane. Dobrze wychowany.
wren romano,
Jak pokazało mi kilka odpowiedzi, gramatyka formalna à la Chomsky to historyczna metoda opisu języków formalnych, która osiągnęła już granice. Wciąż szukam dobrego przeglądu gramatyki formalnej, która nie koncentruje się na teorii złożoności, ale dziękuję za wszystkie dalsze odniesienia! Przyjmę odpowiedź mgalle'a, ponieważ do tej pory ma najmniejszą reputację.
Jakob,
2
W informatyce projektowanie języka komputerowego, projektowanie i programowanie, gramatyki i języki bezkontekstowe oraz wyrażenia regularne i języki są podstawowym sprzętem roboczym i tak ważnym jak zawsze. Ale z drugiej strony, dla dowolnych gramatyk, LBA i języków kontekstowych, widziałem niewiele aplikacji lub wcale.
reinierpost

Odpowiedzi:

20

Z tego, co widziałem w społeczności przetwarzania języka naturalnego, gramatyki formalne à la Chomsky nie są już tak często używane. Oni (również) uważają, że Chomsky Hierarchia jest przestarzała do modelowania języka.

To, co zajęło jego miejsce, to takie rzeczy, jak reguła przepisywania (algorytm Larsa), modele zależności (Dan Klein), gramatyka substytucji drzewa (model DOP), gramatyka funkcji binarnych (Alex Clark).

mgalle
źródło
Po ponownym przeczytaniu mojej odpowiedzi brzmi to bardziej negatywnie, niż chciałem. RL i CFL nigdy nie miały być realistycznymi modelami języka naturalnego, a większość „nowych” modeli jest w nich naprawdę zainspirowana.
mgalle
Myślałem, że RL nie został nawet zaprojektowany jako model języków naturalnych, ale jako model niektórych zachowań systemu. [Oryginalny tekst Kleene również nie używa formalnej terminologii językowej.]
DG_
26

W skrócie: tak.

W szczególności: Chomsky był jednym z pierwszych, którzy sformalizowali hierarchię dotyczącą języków, gramatyki i automatów. Ten wgląd jest nadal bardzo istotny i jest nauczany na wszystkich kursach wprowadzających do teorii automatów. Jednak konkretna hierarchia, którą wymyślił Chomsky, a nazwy elementów hierarchii nie są już tak naprawdę znaczące. Od tego czasu wynaleźliśmy wiele formalizmów, które mieszczą się między poziomami hierarchii Chomsky'ego, powyżej lub poniżej niej. Imiona, których używał Chomsky, nie są szczególnie interesujące, tzn. Nie opierają się na interesującej mierze złożoności ani niczym, są tylko liczbami. Czy językami łagodnie kontekstowymi powinny być Type-1.5, Type-1.7 lub Type-1.3? Kogo to obchodzi. „Lekko wrażliwa na kontekst” to znacznie bardziej informacyjna nazwa.

Zoo Złożoność jest nieco inne, ponieważ jest pełne wszelkiego rodzaju równoważności warunkowej i tym podobne. Bardziej nowoczesna hierarchia teorii automatów nie byłaby liniowa (np. Porównaj CFG vs PEG), ale nadal miałaby dobrze znaną topologię. Aby spojrzeć na współczesną teorię automatów, powinieneś zapoznać się z pracą nad bibliotekami kombinatora parserów i niektórymi zagadnieniami związanymi z unifikacją i teorią typów (choć obie te gałęzie są bardzo odległe).

strzyżyk romano
źródło
4
Znaleźliśmy lepsze nazwiska, tak. Nie oznacza to, że wyniki są nieaktualne.
Raphael,
4
@Raphael: Nieaktualność nie wynika z samych nazw, lecz z tego, że określona hierarchia wprowadzona przez Chomsky'ego nie jest już używana. Inkluzje opisane przez hierarchię Chomsky'ego są (a) nadal prawidłowe i (b) wśród inkluzji w dowolnej współczesnej hierarchii; ale hierarchia Chomsky'ego jako taka nie jest szczególnie istotna, z wyjątkiem tego, że zdarza się, że uderza w niektóre ze znanych wysokich punktów. Ludzie nie prowadzą już badań nad hierarchią Chomsky'ego, prowadzą badania gdzie indziej. To nie jest tak, że wieża wielomianowa ma powody dla swoich nazw / struktur.
wren romano,
26

Jeśli cokolwiek w TCS jest nieaktualne, to ta hierarchia włączania niewielkiego podzbioru klas złożoności była znana / uważana za interesującą w 1956 roku.

Spoczywaj w pokoju, Hierarchio Chomsky'ego i niech już nie prześladujesz programu nauczania teorii licencjata.

Scott Aaronson
źródło
12
Jak kiedyś krzyknął Juris Hartmanis: „A co z zajęciami Chomsky'ego? Zajęcia Chomsky'ego to obrzydliwość !!”
Ryan Williams
1
Ryan: Pamiętam też, że Juris nazywał CH „obrzydliwością”! Gdy pisałem odpowiedź, zastanawiałem się, czy chciałby, aby jego uwaga została upubliczniona. Ale znasz go lepiej niż ja ... :-D
Scott Aaronson
Ten komentarz może być motywowany przynajmniej pejoratywnym poglądem niektórych teoretycznych informatyków i matematyków na językoznawstwo i inne „słabe” nauki: xkcd.com/435 . Ale na pewno dzisiejsza hierarchia Chomsky'ego przesłania pogląd na współczesną teorię złożoności, więc to odpowiada na moje pytanie. Byłoby miło mieć aktualizację na początek w programie nauczania teorii licencjackiej, szczególnie jeśli bardziej interesują Cię formalne języki i gramatyki do praktycznych zastosowań.
Jakob,
1
Hierarchia Chomsky'ego wymienia klasy języków uporządkowane według złożoności opisu, a nie złożoności obliczeń, co zwykle implikuje się, gdy używa się terminu „teoria złożoności”. Są oczywiście powiązane. W każdym razie nadal nie widzę, w jaki sposób jedna (szorstka) hierachia może przysłonić bardziej wyrafinowane klasy, których z trudem można zrozumieć bez pochodzenia z hierarchii Chomsky'ego. To są drzwi wejściowe!
Raphael
20

Jeśli weźmiesz pod uwagę Hierarchię Chomsky'ego z „nowoczesnymi” nazwami (tj. REG, LIN, CFL, CSL, RE odpowiednio DFA / NFA, PDA, LBA, TM), mówię: Nie, to nie jest przestarzałe!

Powód 0 : Nadal jest poprawny w tym sensie, że jego definicje i wyniki nie są sprzeczne z nowszą wiedzą.

Powód 1 : Te klasy / modele obliczeniowe są nadal pierwszymi, których uczysz - ponieważ są proste i dobrze przestudiowane. Spróbuj nauczyć automatu LR licencjata bez uprzedniego omówienia DFA / DPDA.

Powód 2 : Klasy są wciąż pierwszymi / głównymi punktami odniesienia dla nowych wynalazków (przejrzałem artykuł o wielu CFG, który oczywiście powiedział: więcej niż CFG, mniej niż CSG). Może to częściowo wynikać z tego, że najpierw się ich uczy, ale także dlatego, że są proste i dobrze się uczyć .

Anti-Reason 3 : Wyniki nie są przestarzałe tylko dlatego, że znaleziono nowe klasy / modele. Zachowują swoją wartość jako podstawy pola, mimo że nie są aktywnie wykorzystywane na granicy badań.

Raphael
źródło
10
„Matematyka nie starzeje się , staje się klasyczna ”. (Niestety nie wiem, komu przypisuje się ten cytat.)
Heinrich Apfelmus,
Nie masz na myśli „NPDA” zamiast „DPDA”? Niektóre języki bezkontekstowe są rozpoznawane tylko przez niedeterministyczne automaty wypychające.
Zsbán Ambrus
@ ZsbánAmbrus Całkiem słusznie; Powinienem napisać tylko „PDA”. Dzięki!
Raphael
Ostatni powód wcale nie jest przekonujący (tak sądzę, że właśnie dlatego jest przeciwny?). Wiele wyników jest nieaktualnych, ponieważ są one uwzględniane, a czasem nawet trywializowane przez inne podejście do tematu. Nie mówię tego w tym przypadku, tylko o tym, że podany powód niewiele mówi. Również gramatyczny nitpick: „przestarzały” nie jest czasownikiem.
Sasho Nikolov
11

Myślę, że to zależy od modelu obliczeniowego. Jeśli weźmiesz pod uwagę skończone / pushdown / itp. automaty jako model obliczeń, wtedy ważna staje się hierarchia Chomsky'ego (patrz na przykład książka Sipsera). Z drugiej strony odgrywa niewielką rolę w modelu obliczeniowym Turinga.

Pomocna może być następująca ilustracja:

Edycja: Języki formalne odgrywają ważną rolę w projektowaniu języków komputerowych (takich jak Java) i kompilatorów, a także w przetwarzaniu języka naturalnego (NLP).

MS Dousti
źródło
Przepraszam András, nie rozumiem twojego komentarza. OP zapytał, czy hierarchia Chomsky'ego jest nieaktualna. Jego rozumowanie było takie, że nie widział go w zoo złożoności itp. Odpowiedziałem, że jeśli uważa automaty za model komputerowy, hierarchia Chomsky'ego staje się aktualna. Ponadto wspomniałem, że klasy tej hierarchii są ważne przy projektowaniu kompilatora i algorytmach NLP. IMHO, to jest całkowicie związane z pytaniem.
MS Dousti
2
Pewnie, że hierarchia Chomsky'ego nie jest tak naprawdę przestarzała, można ją znaleźć w większości wprowadzeń informatyki teoretycznej, języków formalnych, projektowania kompilatorów itp. Ale poza tym wydaje się, że nie ma nic nowego do powiedzenia. Myślę, że języki podziękowań między REG a CFL i między CFL mogą mieć również znaczenie. Czy to po prostu zły pomysł, aby rozszerzyć hierarchię o te języki, ponieważ hierarchia Chomsky'ego ma zapach „przestarzałego” jako nieistotnego dla obecnych badań?
Jakob
Nie sądzę, że to zły pomysł, choć trzeba znaleźć aplikację, do której pasuje nowe rozszerzenie.
MS Dousti