Pytania otagowane jako grammars

2
Czy { } nie jest kontekstowe?
Czy język { } jest bezkontekstowy?zajabjotdok | i≠j,i≠k,j≠k aibjck | i≠j,i≠k,j≠ka^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k Uświadomiłem sobie, że spotkałem prawie wszystkie warianty tego pytania z różnymi warunkami dotyczącymi związku między i, j i k, ale nie tym. Domyślam się, że nie jest pozbawiony kontekstu, …
4
Jaki jest najpotężniejszy parser?
Jako poboczny projekt piszę język przy użyciu Pythona. Zacząłem od użycia klonu Flex / Bison o nazwie Ply, ale zbliżam się do krawędzi tego, co mogę wyrazić za pomocą tego stylu gramatyki, i nie jestem zainteresowany zhakowaniem mojego języka z powodu niedopasowania impedancji z narzędzie. Dlatego nie jestem przeciwny pisaniu …
4
Dowód lematu pompowania dla języków bezkontekstowych za pomocą automatów pushdown
Lemat o pompowaniu dla języków regularnych może być udowodnione przez rozważa automat skończony, który rozpoznaje stan języka badanego, zbierając ciąg o długości większej niż jego liczby stanów i stosując zasadę zaszufladkować. Jednak pompowanie lematu dla języków bezkontekstowych (a także lematu Ogdena, który jest nieco bardziej ogólny), zostało udowodnione poprzez rozważenie …
1
Czy można rozstrzygać o równoważności jednoznacznych języków bezkontekstowych?
Dobrze wiadomo, że problem równoważności jest nierozstrzygalny dla ogólnych języków bezkontekstowych. Jednak wszystkie dowody tego faktu, o których jestem świadomy, wydają się obejmować pewne niejednoznaczne gramatyki bezkontekstowe. Z tego powodu chciałbym zapytać, czy wiadomo, czy problem pozostaje nierozstrzygalny, ograniczając się do jednoznacznych języków bezkontekstowych. To znaczy, biorąc pod uwagę dwie …
4
Reprezentacje base-k w domenie wielomianu - czy jest ona pozbawiona kontekstu?
W rozdziale 4 Drugiego kursu teorii automatu Jeffreya Shallita następujący problem wymieniono jako otwarty: p(n)p(n)p(n)∈Np(n) \in \mathbb{N}n∈Nn \in \mathbb{N} { p ( n ) ∣ n ⩾ 0 }){p(n)∣n⩾0}\{p(n) \mid n \geqslant 0\} jest pozbawione kontekstu, tylko wtedy, gdy stopieńwynosi.ppp ⩽ 1⩽1\leqslant 1 Jaki jest teraz jego status (na październik …
1
Dolne granice wielkości CFG dla określonych języków skończonych
Rozważ następujące naturalne pytanie: Biorąc pod uwagę skończony język , jaka jest najmniejsza bezkontekstowa gramatyka generująca ?L.L.LL.L.L Możemy uczynić pytanie bardziej interesującym, określając sekwencję języków , na przykład jest zbiorem wszystkich permutacji : intuicyjnie, CFG dla „musiałby” mieć rozmiar . Jesteśmy więc zainteresowani asymptotycznym rozmiarem najmniejszych CFG dla języków.L.nL.nL_nL.nL.nL_n{ 1 …
2
Czy istnieje wielowymiarowa gramatyka generatywna?
Interesuje mnie muzyka komputerowa, w której istnieją podejścia do traktowania utworów muzycznych jako zdań w gramatyce generatywnej lub systemach L. Zamiast komponować, można określić gramatykę i pozwolić komputerowi na generowanie muzyki. Np. Grupa Yale wokół zmarłego Paula Hudaka jest w tym bardzo silna. To uderzyło mnie, że używamy reprezentacje pozornie …
9 grammars 
1
Asymptotyczna gęstość niejednoznacznych gramatyk bezkontekstowych (CFG)
Jaki jest stosunek niejednoznacznych CFG do wszystkich CFG ? Ponieważ oba zestawy są w nieskończoność nieskończone, stosunek nie jest dobrze zdefiniowany. Ale co z asymptotyczną gęstością : limn ↦ ∞# niejednoznaczny CFG o rozmiarze < n# CFG o wielkości < nlimn↦∞# niejednoznaczny CFG wielkości<n# CFG wielkości<n\lim_{n \mapsto \infty}\frac {\# \text{ …
1
Czy istnieje wielomianowy rozmiar CFG opisujący ten skończony język?
Czy istnieją permutacje i wielkość wielomianowa (w ) gramatyka bezkontekstowa opisująca język skończony zamiast alfabetu ?π1,π2π1,π2\pi_1,\pi_2|w|=n|w|=n|w|=n{wπ1(w)π2(w)}{wπ1(w)π2(w)}\{w \pi_1(w) \pi_2(w)\}{0,1}{0,1}\{0,1\} AKTUALIZACJA: Dla jednej permutacji jest to możliwe. jest odwróceniem lub względnie niewielką modyfikacją odwrócenia.ππ\piππ\pi
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.