Pytania otagowane jako context-free

1
Wystarczające warunki dla prawidłowości języka bezkontekstowego
Byłoby miło zebrać listę warunków, które sugerują, że bezkontekstowy język L jest regularny, tj. Warunki postaci: „jeśli dany CFG / PDA ma właściwość P, to jego języki są regularne” Właściwość P nie musi charakteryzować CFG generujących zwykłe języki. Ponadto P nie musi być rozstrzygalne, a P powinno „w jakiś sposób …
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 …
1
Czy {ww '| HamDist (w, w ')> 1} bez kontekstu?
Po przeczytaniu ostatniego pytania „Czy uzupełnienie pozbawione kontekstu?” {www∣...}{www∣...}\{ www \mid ...\}; Przypomniałem sobie podobny problem, którego nie byłem w stanie odeprzeć: Czy bez kontekstu?L={ww′∣w,w′∈{0,1}∗∧|w|=|w′|∧HamDist(w,w′)>1}L={ww′∣w,w′∈{0,1}∗∧|w|=|w′|∧HamDist(w,w′)>1}L = \{ ww' \mid w,w' \in \{0,1\}^* \land |w|=|w'| \land HamDist(w,w')>1 \} Tutaj wymagamy, aby dwa struny różniły się co najmniej w dwóch pozycjach (odległość …
2
Czy SAT jest językiem bezkontekstowym?
Rozważam język wszystkich zadowalających formuł logicznych zdań, SAT (aby upewnić się, że ma to skończony alfabet, będziemy kodować litery zdań w odpowiedni sposób [edytuj: odpowiedzi wskazały, że odpowiedź na pytanie może nie być solidna pod różne kodowania, więc trzeba być bardziej szczegółowym - patrz moje wnioski poniżej] ). Moje proste …
3
Dwuznaczność w zwykłych i pozbawionych kontekstu językach
Rozumiem następujące twierdzenia, które są prawdziwe: Dwie różne pochodne łańcucha w danym CFG mogą czasem przypisywać to samo drzewo parsowania łańcuchowi. Kiedy w danym CFG występują pochodne jakiegoś łańcucha, które przypisują różne drzewa parsowania, CFG jest niejednoznaczny. Niektóre języki bezkontekstowe generowane przez niejednoznaczne CFG są również generowane przez jednoznaczne CFG. …
1
Problem członkostwa dla niektórych klas gramatyki nieograniczonej
Rozważ dowolną bezkontekstową gramatykę nad alfabetem . Do produkcji tej gramatyki dodaj dwie stałe produkcje bezkontekstowe : i \ overline {1} 1 \ rightarrow \ epsilon . Nazwij wynikową gramatykę G ^ P oznaczającą „ G uzupełniony o produkcje P ”.solGG{ 0 , 1 ,0¯¯¯,1¯¯¯}{0,1,0¯,1¯}\lbrace 0,1,\overline{0} ,\overline{1} \rbraceP.PP0¯¯¯0 → ϵ0¯0→ϵ\overline{0} …
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.