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...
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...
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...
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...
To jest przeformułowanie Czy programy gramatyczne? poprzednio zadane przez Vag i z wieloma sugestiami komentujących. W jaki sposób można postrzegać gramatykę jako model obliczeń? Jeśli na przykład weźmiemy prostą gramatykę bezkontekstową, taką jak G ::= '1' -> '0' '+' '1' '1' -> '1' '+'...
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...
Niech będzie językiem bezkontekstowym. Zdefiniować p p c ( L ) za przed i przyrostek zamknięcie L , innymi słowy, p p c ( L ) obejmują L jest prefiks i postfixes i stąd L siebie. Moje pytanie: jeśli L jest pozbawiony kontekstu i ma niejednoznaczną gramatykę, to czy to samo dotyczy p p c ( L )...
Niech zostanie podana liczba . Rozważ następujący język .nnnL.n= {w w|w ∈ { 0 , 1 }n}Ln={ww|w∈{0,1}n}L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \} słowy, jest zbiorem ciągów kopii o długości . 2 nL.nLnL_n2 n2n2n Rozważmy następujący stan złożoność funkcji takie, że jest liczbą stanów w...
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...
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...
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...