Pytania otagowane jako fl.formal-languages

języki formalne, gramatyka, teoria automatów

4
Liczenie słów przyjętych przez zwykłą gramatykę
W przypadku zwykłego języka (NFA, DFA, gramatyki lub wyrażenia regularnego), jak można policzyć liczbę słów akceptowanych w danym języku? Interesujące są zarówno „z dokładnie n literami”, jak i „z najwyżej n literami”. Margareta Ackerman ma dwa artykuły na powiązany temat wyliczania słów zaakceptowanych przez NFA, ale nie byłem w stanie …
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 …
5
Odzyskiwanie parsowanego lasu z parsera Earley?
Niedawno czytałem parser Earley i uważam, że jest to jeden z najbardziej eleganckich algorytmów, jakie do tej pory widziałem. Jednak algorytm w tradycyjnym znaczeniu jest rozpoznawaczem, a nie analizatorem składni, co oznacza, że ​​może wykryć, czy łańcuch pasuje do określonego CFG, ale nie wygenerować dla niego drzewa analizy. Moje pytanie …
2
Gramatyka i typy wrażliwe na kontekst
1) Jaki, jeśli w ogóle, jest związek między pisaniem statycznym a gramatyką formalną? 2) Czy w szczególności byłoby możliwe, aby automat z ograniczeniem liniowym sprawdził, czy, powiedzmy, program C ++ lub SML był dobrze napisany? Automat zagnieżdżonego stosu? 3) Czy istnieje naturalny sposób na wyrażenie zasad pisania statycznego w formalnych …
1
Języki rozpoznawane przez DFA wielkości wielomianowej
W przypadku ustalonego skończonego alfabetu język formalny L ponad Σ jest regularny, jeśli istnieje deterministyczny automat skończony (DFA) ponad ΣΣΣ\SigmaLL.LΣΣ\SigmaΣΣ\Sigma który akceptuje dokładnie .LL.L Interesują mnie języki, które są „prawie” regularne w tym sensie, że mogą być rozpoznawane przez rodziny automatów wielkości, które rosną tylko wielomianowo wraz z długością słowa. …
6
Zaawansowane techniki określania dolnych granic złożoności
Niektórzy z was mogli śledzić to pytanie , które zostało zamknięte z powodu braku poziomu badań. Wyciągam więc część pytania, która jest na poziomie badawczym. Oprócz „prostszych” technik, takich jak redukcja do sortowania lub problem z WYŁĄCZENIEM, jakie techniki zostały zastosowane, aby udowodnić dolne granice złożoności problemu w czasie? W …
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 …
2
Numer podziału protokołu i deterministyczna złożoność komunikacji
Oprócz (deterministycznej) złożoności komunikacji cc(R)cc(R)cc(R) relacji RRR , inną podstawową miarą ilości potrzebnej komunikacji jest numer podziału protokołu pp(R)pp(R)pp(R) . Zależność między tymi dwoma miarami jest znana aż do stałego współczynnika. Monografia Kushilevitza i Nisana (1997) daje cc(R)/3≤log2(pp(R))≤cc(R).cc(R)/3≤log2⁡(pp(R))≤cc(R).cc(R)/3 \le \log_2(pp(R)) \le cc(R). Jeśli chodzi o drugą nierówność, łatwo jest podać …
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 …
5
Specjalna klasa języków: języki „okrężne”. Czy to jest znane
Zdefiniuj następującą klasę języków „okrągłych” nad skończonym alfabetem Sigma. W rzeczywistości nazwa już istnieje, aby oznaczać inną rzecz, która się wydaje, stosowana w dziedzinie przetwarzania DNA. AFAICT, to inna klasa języków. Język L jest okrągła wtw dla wszystkich słów w , mamy:wwwΣ∗Σ∗\Sigma^* www należy do L wtedy i tylko wtedy, …
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 …
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.