Pytania otagowane jako context-free

1
Racjonalna hierarchia nieracjonalnych automatów i języków Eilenberga - gdzie jest teraz?
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 znajdują się na dole tej hierarchii. W górę napotyka się zjawiska …
3
Czy istnieje rozszerzenie wyrażeń regularnych, które wychwytują języki bezkontekstowe?
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 S →S→aSbS.→zaS.bS \to a S b S→aaSbS.→zazaS.bS \to …
1
Czy wszystkie jednoznaczne gramatyki można analizować w czasie liniowym?
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 :O(n2)O(n2)O(n^2) Czy wszystkie jednoznaczne gramatyki można analizować w czasie liniowym? Jestem …
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 …
3
Analiza CFG przy użyciu spacji
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, nie mam pojęcia, jakie jest użycie przestrzeni przez ten algorytm mnożenia macierzy). Zastanawiałem się, czy …
2
Odniesienie do „bardziej algebraicznego” podejścia do automatów wypychających i świetlówek kompaktowych?
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 bezkontekstowe i automaty wypychające są poza zakresem książki. Zdaję sobie sprawę z niektórych …
1
Charakterystyka dla której nie jest CFL?
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 nieskończony i regularny nie jest „wystarczający”, aby nie …
1
Czy DPDA bez ruchów
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 automaty są równe mocy DPDA?ϵϵ\epsilonϵϵ\epsilon Może …
1
Czy istnieją warianty widocznych automatów przesuwających, które umożliwiają wypychanie słów na stos?
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 cel.ϵϵ\epsilon Oczywiście, takie warianty mogą być tworzone, ale zastanawiam się, czy to rujnuje właściwości zamknięcia …
2
Zwroty permutacyjne z analizą LR
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 zainteresowani kolejnością tych nieterminali.{ A1, … , An}{ZA1,…,ZAn}\{ A_1, \dots, …
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.