W przedmowie do swoich bardzo wpływowych książek Automata, języki i maszyny (tomy A, B) Samuel Eilenberg kusząco obiecał tomy C i D dotyczące „hierarchii (zwanej racjonalną hierarchią) nieracjonalnych zjawisk… przy użyciu relacji racjonalnych jako narzędzie do porównywania. Racjonalne zestawy...
W wielu artykułach dotyczących gramatyk bezkontekstowych (CFG), przykłady takich gramatyk tam często dopuszczają łatwą charakterystykę generowanego języka. Na przykład: S →S→aaSbS.→zazaS.bS \to a a S b S→S.→S \to generuje ,{a2ibi|i≥0}{za2)jabja|ja≥0}\{ a^{2i} b^i | i \geq 0\} S → a a S b...
W praktyce, dla języka, który można ostatecznie skompilować / przekształcić w instrukcje na poziomie systemu, czy konieczne jest, aby była to gramatyka bezkontekstowa? np .: Czy wszystkie języki programowania / skryptów są wolne od kontekstu? Java oparta jest na CFG, ale czy w rzeczywistości...
Podczas majstrowania przy niekanonicznym analizowaniu LR wymyśliłem metodę analizy (z tabelami o nieskończonych rozmiarach, co czyni ją nieco niepraktyczną ), która jest w stanie przeanalizować dokładnie jednoznaczne gramatyki w czasie , i zastanawiałem się, czy można to zrobić lepiej...
Szukam języków, które „prawdopodobnie nie są wolne od kontekstu”, ale nie jesteśmy w stanie (nie) udowodnić tego przy użyciu znanych standardowych technik. Czy jest ostatnia ankieta na ten temat lub otwarta sekcja problemowa z ostatniej konferencji? Prawdopodobnie nie ma wielu języków, o...
Oznacz przez wnwnw_n liczbę słów o długości nnn w (możliwie niejednoznacznym) języku bezkontekstowym. Co wiadomo o wnwnw_n ? Jestem pewien, że dużo się tego badano, ale nie mogłem w ogóle nic
Biorąc pod uwagę wyrażenia regularne , czy istnieją jakieś nietrywialne granice wielkości najmniejszej kontekstowej gramatyki dla ?R1, … , RnR1,…,RnR_1, \dots, R_nR1∩ ⋯ ∩ RnR1∩⋯∩RnR_1 \cap \cdots \cap
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...
Czytałem gdzieś, że maszyna Turinga nie może tego obliczyć i dlatego jest nierozstrzygalna, ale dlaczego? Dlaczego komputer nie jest w stanie wygenerować parsowania drzewa i podjąć decyzji? Może się mylę i da się to
Istnieje wiele algorytmów, które mogą analizować gramatykę bezkontekstową w czasie . Używając mnożenia macierzy, można nawet iść asymptotycznie szybciej.O(n3)O(n3)O(n^3) Jednak wszystkie algorytmy do analizy dowolnych CFG, które znam, mają najgorsze wykorzystanie przestrzeni (chociaż, co prawda,...
W książce Sakarovitcha na temat teorii automatów jest napisane we wstępie do części dotyczącej racjonalności w wolnej grupie, że przedstawiony w niej materiał stanowi „fundament prawdziwie matematycznej teorii języków bezkontekstowych”. Nie jest to jednak jednoznaczne, ponieważ języki...
Wyrażenie permutacji jest rozszerzeniem standardu (E) BNF wolne definicji kontekstu gramatyczne: frazę permutacji zawiera n produkcji (lub równoważnie nieterminale) A 1 przez A n . W miejscu wyrażenia permutacyjnego chcielibyśmy zobaczyć każdą z tych produkcji dokładnie raz, ale nie jesteśmy...
Zastanawiam się, czy są jakieś dokumenty lub badania dotyczące widocznych automatów przesuwających w dół, ale pozwalające na wypychanie słów zamiast pojedynczych liter na stos. Alternatywnie, konstrukcja umożliwiająca wypychanie symboli na -transitions może osiągnąć ten sam...
W formalnym opisie deterministycznych automatów wypychających pozwalają one na ruchy , w których maszyna może wyskakiwać lub pchać symbole na stos bez odczytywania symbolu z wejścia. Jeśli te ϵ ruchy są niedozwolone, a stos można zmodyfikować tylko raz po odczytaniu każdego symbolu, czy wynikowe...
Jest to standardowy dowód w kursach z automatami, że dla i że nie jest językiem bezkontekstowym.L=Σ⋆L=Σ⋆L = \Sigma^\star|Σ|≥2|Σ|≥2|\Sigma| \ge 2S(L)={ww:w∈L}S(L)={ww:w∈L}S(L) = \{ww : w \in L\} Prawdą jest również, że dla każdego skończonego , jest skończone (a zatem CFL). Zgaduję, że jest...
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...
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...
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
Języki Dyck definiuje następująca gramatyka S → S S.Dyck(k)Dyck(k)\mathsf{Dyck}(k) nad zbiorem symboli { ( 1 , … , ( k , ) 1 , … , ) k } . Języki intuicyjnie Dyck są językami zbilansowanych nawiasów k innego rodzaju. Na przykład (S→SS|(1S)1|…|(kS)k|ϵS→SS|(1S)1|…|(kS)k|ϵ S \rightarrow SS \,|\, (_1...
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 -...