Zdecydowane języki niewrażliwe na kontekst

Można argumentować, że większość języków stworzonych do opisywania codziennych problemów ma charakter kontekstowy. Z drugiej strony jest możliwe i nietrudno znaleźć niektóre języki, które nie są rekurencyjne, a nawet nie są wymienne.

Pomiędzy tymi dwoma typami znajdują się rekurencyjne języki beztekstowe. Wikipedia podaje tutaj jeden przykład :

Przykładem języka rekurencyjnego, który nie jest zależny od kontekstu, jest każdy język rekurencyjny, którego decyzja jest trudnym problemem EXPSPACE, powiedzmy, zestaw par równoważnych wyrażeń regularnych z potęgowaniem.

Więc pytanie: jakie inne problemy istnieją, które można rozstrzygać, ale nie uwzględniają kontekstu? Czy ta klasa problemów jest taka sama, jak trudna do rozstrzygnięcia EXPSPACE?

CSL jest taki sam jak $\mathsf{NSpace}(n)$ (niedeterministyczna przestrzeń liniowa). Każdy język spozanie jest CSL.$\mathsf{NSpace}(n)$

Aby poczuć sytuację, pamiętaj, że a nawet TQBF.$SAT \in \mathsf{NSpace}(n)$

Jakie jeszcze istnieją problemy, które można rozstrzygnąć, ale które nie uwzględniają kontekstu?

Jest wiele problemów. Zrobi to każdy problem, który jest kompletny dla klasy złożoności większej niż (potrzebujemy P S p a c $\mathsf{PSpace}$$\mathsf{PSpace}$ ponieważ problemy takie jak TQBF w które są kompletne dla P S p a c $\mathsf{NSpace}(n)$$\mathsf{PSpace}$ponieważ redukcja (czas wielomianowy) może wysadzić wielkość wejścia przez wielomian). Podanie przykładu będzie oznaczało udowodnienie dolnej granicy dla klasy złożoności zawierającej problem i jest to bardzo, bardzo trudne zadanie. Jedynym głównym sposobem, jaki znamy do tej pory, jest diagonalizacja, która intuicyjnie oznacza, że ​​większa klasa powinna być w stanie symulować klasę mniejszą.

Więc wydaje się naturalnym miejscem, w którym można zacząć szukać naturalnych przykładów języka, które nie są CSL.$\mathsf{ExpSpace\text{-}hard}$

Czy ta klasa problemów jest taka sama, jak trudna do rozstrzygnięcia EXPSPACE?

Nie. Według twierdzenia o hierarchii przestrzeni istnieją języki, które są w których nie ma w N S p a c e ( n ) . Jeśli poprosisz o ładne przykłady, będzie to trudne, ponieważ twierdzenie działa z wykorzystaniem diagonalizacji, a zatem język, który okazuje się spełniać te warunki, jest bardzo sztuczny.$\mathsf{NSpace}(n^2)$$\mathsf{NSpace}(n)$

Sugeruję, abyś zadał osobne pytanie dotyczące naturalnego problemu, który dzieli $\mathsf{NSpace}(n^2)$ od .$\mathsf{NSpace}(n)$

Podobnie jak jest pozbawiony kontekstu, ale nie regularny, język L = { a n b n c n : n ≥ 0 } jest rozstrzygalny, ale nie kontekstowy. Jednak L można rozwiązać za pomocą przestrzeni logarytmicznej (potrzebujesz tylko licznika dla każdego z symboli a , b i c ), więc nie jest on trudny w trybie EXSPACE.$\{a^nb^n:n\geq 0\}$$L=\{a^nb^nc^n:n\geq 0\}$$L$$a$$b$$c$

Również język , gdzie r 1 i r 2 są wyrażeniami regularnymi, jest kompletny z PSPACE. Jestem prawie pewien, że nie jest zależny od kontekstu, ale nie pamiętam dowodu i piszę z telefonu, więc nie jest łatwo szukać referencji.$\{(r_1,r_2):L(r_1)=L(r_2)\}$$r_1$$r_2$