Czy wszystkie języki bezkontekstowe i zwykłe są skutecznie rozstrzygalne?

Natknąłem się na ten rysunek, który pokazuje, że języki kontekstowe i zwykłe są (odpowiednimi) podzbiorami sprawnych problemów (podobno ). Doskonale rozumiem, że wydajne problemy stanowią podzbiór wszystkich rozstrzygalnych problemów, ponieważ możemy je rozwiązać, ale może to zająć bardzo dużo czasu. $\mathrm{P}$

Dlaczego wszystkie bezkontekstowe i regularne języki są skutecznie rozstrzygalne? Czy to oznacza, że ich rozwiązanie nie potrwa długo (to znaczy znamy to bez większego kontekstu)?

wprowadź opis zdjęcia tutaj

— Gigili
źródło

Z ciekawości, gdzie znalazłeś tę postać? Pomocne może być wyjaśnienie kontekstu, ponieważ „efektywność” nie jest formalnym pojęciem, a różni ludzie mogą używać go do oznaczania różnych rzeczy.

— Gilles „SO- przestań być zły”

Jeśli „wydajny” oznacza „

” (co jest powszechne), „wydajny” nie oznacza „niezbyt długi czas”, ponieważ wielomian również daje ogromne wartości. Zauważ, że podstawowym skutkiem złożoności jest to, że istnieją nieskończone sekwencje problemów, każdy odpowiednio łatwiejszy niż następny. Dotyczy to zarówno wewnątrz jak i na zewnątrz

\in P

$\in \mathrm{P}$

P

$\mathrm{P}$

— Raphael

@Raphael: W tym kontekście wydajna jest klasa języków, które można rozstrzygać w czasie wielomianowym. Użyłem „może to zająć bardzo dużo czasu” w przypadku rozstrzygających problemów, w przeciwieństwie do nierozstrzygniętych, dla których nie możemy znaleźć rozwiązania w żadnym określonym czasie.

— Gigili,

poprawnym technicznym sposobem na stwierdzenie, że jest to, że określenie, czy w∈L gdzie w jest słowem, a L jest językiem, jest w P. tj. / aka „rozpoznawanie języka”

— wer

Odpowiedzi:

$\cal{O}(n)$

$\cal{O}(n^3)$

$\sf{P}$ $\sf{EXPTIME}\setminus \sf{P}$

— Dave Clarke
źródło

Warto wspomnieć o algorytmie mnożenia macierzy dla gramatrów bezkontekstowych, który ma lepszy czas działania i że ten algorytm działa bardzo skutecznie (liniowo) na praktycznie każdej gramatyce bezkontekstowej: sciencedirect.com/science/article/pii / 030439759190180A

— Alex ten Brink

@AlextenBrink Nie sądzę, aby to pytanie wymagało drobniejszej ziarnistości niż „wielomianowy czy nie”.

— Raphael

O (n)

$O(n)$

W rzeczywistości w przypadku zwykłych języków nawet nie potrzebujesz jawnie automatów deterministycznych. Symulujesz wszystkie obliczenia równolegle, śledząc wszystkie stany w ten sposób naśladując konstrukcję zestawu zasilającego.

— Hendrik,

@Dave: liniowy w długości ciągu wejściowego, dla ustalonego języka regularnego, podobnie jak inne podane tutaj złożoności.

— Hendrik,

Uściślenie / „drobny druk” po odpowiedzi przez DC: wszystkie świetlówki kompaktowe w postaci normalnej formy Chomsky'ego można skutecznie przeanalizować za pomocą algorytmu CYK, a wszystkie świetlówki kompaktowe można przekonwertować na CNF. Jednak konwersja arbitralnej CFL na CNF może zająć przestrzeń wykładniczą w najgorszym przypadku, w zależności od niektórych algorytmów. (Nie znam algorytmu, który gwarantuje tutaj konwersję czasu P, czy ktoś jeszcze? Trzeba wziąć pod uwagę wszystkie skrajne / najgorsze przypadki, takie jak niedeterministyczne CFL lub dwuznaczne .) Wikipedia w sekcji CNF Porządek przekształceń

$|G|^2$ $2^{2 |G|}$

Dlatego wydaje się, że mogą istnieć świetlówki kompaktowe, których nie da się skutecznie przeanalizować. Większość języków programowania można skutecznie przekonwertować na CNF (lub być może głównie zdefiniowane w CNF lub w pobliżu CNF), dlatego parsowanie CFL dla „typowych” języków jest „praktycznie” u P. Prawdopodobnie istnieją pewne współczesne badania nad tym najgorszym złożonością (ale nie znajdź najnowsze artykuły na ten temat dotyczące wyszukiwania pobieżnego). Np. Ten starszy (1973) artykuł badawczy Greibacha również wydaje się wskazywać, że wydajność najgorszego przypadku może nie być ograniczona przez P. patrz np.

Najtrudniejszy język bezkontekstowy / Greibach

— vzn
źródło