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