Złożoność przecięcia zwykłych języków jako gramatyki bezkontekstowej

Biorąc pod uwagę wyrażenia regularne , czy istnieją jakieś nietrywialne granice wielkości najmniejszej kontekstowej gramatyki dla ? $R_1, \dots, R_n$ $R_1 \cap \cdots \cap R_n$

fl.formal-languages regular-language context-free

— Max
źródło

??? próbując to wyobrazić. czy jest jakaś sztuczka? przecięcie jest regularne. można znaleźć minimalną DFA (liczba stanów wrt) standardowymi metodami, które są również CFG.

R_{n}

$R_n$

— vzn

@vzn: masz rację. Problem polega na tym, że ten DFA, a zatem CFG, może być bardzo duży. Zastanawiam się, czy można użyć dodatkowej mocy CFG, aby uzyskać bardziej zwięzły opis skrzyżowania.

— Maks.

nie przypuszczać. podejrzewam, że każda CFL, która rozpoznaje (tj. jest równoważna) RL, nie używa swojego stosu lub może zostać przekonwertowana na taki, który nie powoduje wzrostu stanów, a minimalny taki PDA (liczba stanów wrt) ma taki sam rozmiar jak minimalny DFA. nigdy nie słyszałem / nie widziałem na to dowodu. to może nie jest trudne? prostsze pytanie, czy jest jakiś PDA, który rozpoznaje RL, który jest mniejszy niż DFA? nie myśl

— vzn

@vzn: Przydatna hipoteza, ale fałsz: niech będzie podzbiorem języków Dyck w dwóch typach nawiasów, w których maksymalna głębokość zagnieżdżenia wynosi . Istnieje CFG dla o rozmiarze , ale minimalny DFA (nawet, jak sądzę, minimalny NFA) ma rozmiar .

L_{k}

$L_k$

k

$k$

L_{k}

$L_k$

O (k)

$O(k)$

O (2^{k})

$O(2^k)$

— Maks.

Języki Dyck to CFL, ale nie RL ...? ale widzisz, że ograniczasz maksymalną głębokość zagnieżdżania ... więc czy możesz zbudować ten sam język za pomocą skrzyżowań RL? co / gdzie jest dowód, że minimalny DFA jest tak duży? czy to stany ? nie definiujesz kryteriów minimalności ani gdzie indziej i przyjmujesz stany jako naturalny przypadek, ale nie jest to jedyny przypadek.

O (2^{k})

$O(2^k)$

— vzn

Odpowiedzi:

To świetne pytanie i naprawdę leży w moich zainteresowaniach. Cieszę się, że o to zapytałeś Max.

Niech podano DFA z co najwyżej stanami. Byłoby miło, gdyby istniał PDA z sub-wykładniczo wieloma stanami, które akceptują przecięcie języków DFA. Sugeruję jednak, że taki PDA może nie zawsze istnieć. $n$ $O(n)$

Rozważ język kopiowania. Teraz ogranicz go do kopiowania ciągów o długości n.

Formalnie rozważ -kopia . $n$ $:=$ $\{ xx \, | \, x \in \{0,1\}^{n}\}$

Możemy reprezentować kopiowanie jako przecięcie DFA o rozmiarze co najwyżej . Najmniejszy DFA, który akceptuje kopiowanie, ma jednak stanów. $n$ $n$ $O(n)$ $n$ $2^{\Omega(n)}$

Podobnie, jeśli ograniczymy się do alfabetu stosu binarnego, podejrzewam, że najmniejszy PDA, który akceptuje kopiowanie, ma wykładniczo wiele stanów. $n$

PS Prosimy o przesłanie mi e-maila, jeśli chcesz omówić dalej. :)

— Michael Wehar
źródło

Nie sądzę, że mogą istnieć jakieś nietrywialne dolne lub górne granice.
W przypadku dolnych granic rozważ język dla ustalonego . Rozmiar najmniejszej bezkontekstowej gramatyki jest logarytmiczny w wielkości wyrażenia regularnego , podczas gdy rozmiar najmniejszego automatu dla jest liniowy w stosunku do wyrażenia regularnego . Ta różnica wykładnicza pozostaje taka sama, jeśli przecinamy z innymi takimi językami. W przypadku górnych granic rozważ język który składa się z dokładnie jednej sekwencji deBruijn o długości . Wiadomo, że rozmiar najmniejszej gramatyki $L_1 = \{ a^{2^k} \}$ $k$ $L_1$ $L_1$ $L_1$ $L_1$
$L_2$ $n$ $L_2$ jest najgorszym przypadkiem, tj. , więc różnica w stosunku do „najmniejszego” automatu dla jest po prostu czynnikiem logarytmicznym, zdanie 1 w $O\left( \frac{n}{\log n} \right)$ $L_2$

D. Hucke, M. Lohrey, E. Noeth Konstruowanie gramatyk małych drzewek i małych obwodów dla formuł , które pojawią się w FSTTCS 2014

Nietrywialna ogólna dolna lub górna granica przeczyłaby tym wynikom, ponieważ to, co jest prawdziwe dla przecięcia języków, musi być prawdziwe dla przecięcia języka. $n$ $1$

— john_leo
źródło

Uwaga na temat wielkości najmniejszej gramatyki singla deBruijn-Sequence jest dość interesująca. Czy możesz podać referencję. Dziękuję Ci.

— Michael Wehar,

Mogę się również mylić, ale wydaje się, że rozwiązałeś problem tylko dla pojedynczego wyrażenia regularnego (zamiast produktu wyrażeń regularnych)?

— Michael Wehar,

n

$n$

Dziękuję Ci! Udało ci się opisać konkretny przykład. Oto prosta uwaga, która prowadzi do istnienia takich przykładów. Niech n będzie dane. Istnieją 2 ^ n ciągów długości n. Ponadto nie ma więcej niż 2 ^ n maszyn Turinga z co najwyżej stanami n / log (n). Dlatego niektóre ciągi x o długości n takie, że żadna maszyna Turinga z stanami mniejszymi niż n / log (n) nie akceptuje języka {x}. Dlatego {x} jest akceptowany przez DFA ze stanami n i nie może być zaakceptowany przez PDA z mniej niż stanami n / log (n).

— Michael Wehar

Pozwólcie, że popieram sąd Michaela, to rzeczywiście interesujące pytanie. Główną ideę Michaela można połączyć z wynikiem z literatury, zapewniając tym samym dolną granicę z rygorystycznym dowodem.

$n$ $k$

$2^{k+1}$ $2^k+1$ $s$ $O(s^2)$ $O(4^{k})$

$2^{\Omega(\sqrt{k}/\log k)}$

$L_n = \{\,ww^Rw \in \{a,b\}^*\mid |w|=n\,\}$ $w^R$ $w$ $L_n$ $2n+1$

$r_i = (a+b)^ia(a+b)^{2(n-i-1)}a(a+b)^*+(a+b)^ib(a+b)^{2(n-i-1)}b(a+b)^*$ $1\le i \le n$
$s_i = (a+b)^*a(a+b)^{2(n-i-1)}a(a+b)^i+(a+b)^*b(a+b)^{2(n-i-1)}b(a+b)^i$ $1\le i \le n$
$\ell = (a+b)^{3n}$

$k$ $O(n^2)$

$L_n$ $2^n/(2n) = 2^{\Omega(\sqrt{k}/\log k)}$ $2$ $n$ $n^n/(2n)$

$O(4^n)$

Bibliografia:

V. Arvind, Pushkar S. Joglekar, Srikanth Srinivasan. Obwody arytmetyczne i iloczyn wielomianów Hadamarda , FSTTCS 2009, t. 4 LIPIcs, s. 25–36
Lange, Martin; Leiß, Hans (2009). „ Do CNF czy nie do CNF? Wydajna, ale reprezentatywna wersja algorytmu CYK ”. Informatica Didactica 8.

— Hermann Gruber
źródło