Pytania o języki formalne, które można opisać wyrażeniami regularnymi (w sensie Kleene) lub, równoważnie, języki, które mogą być akceptowane przez automaty skończone.
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...
Dlaczego języki regularne (i te wyrażenia regularne) nazywane są „regularnymi”? Dużo prawidłowości występuje również w językach bezkontekstowych i innych rodzajach języków. Przypuszczam, że na początku zastosowano przymiotnik „zwykły” w celu odróżnienia tego rodzaju języków od innych...
Definiujemy zwykły język drzewa, tak jak w książce TATA : Jest to zestaw drzew akceptowany przez niedeterministyczny automat skończonego drzewa (rozdział 1) lub, równoważnie, zbiór drzew wygenerowany przez zwykłą gramatykę drzewa (rozdział 2). Oba formalizmy są bardzo podobne do znanych analogów...
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...
Niech będą dwoma zwykłymi językami podanymi przez NFA M_1 jako dane wejściowe.M 1 , M 2L.1, L2)L1,L2L_1,L_2M.1, M2)M1,M2M_1,M_2 Załóżmy, że chcielibyśmy sprawdzić, czy . Można to wyraźnie zrobić za pomocą algorytmu kwadratowego, który oblicza automat produktu , , ale zastanawiałem się, czy wiadomo...
I ustalić język regularny na alfabetem , i rozważmy następujący problem, który ja nazywam się harmonogram dla . Nieoficjalnie, dane wejściowe dają mi liter i odstępy dla każdej litery (tj. Minimalną i maksymalną pozycję), a moim celem jest umieszczenie każdej litery w tym przedziale, tak aby żadne...
Zauważyłem, że zwykłe języki nad alfabetem można naturalnie traktować jako zestaw, a nawet sieć. Co więcej, konkatenacja wraz z pustym językiem określa ścisłą strukturę monoidalną w tej kategorii, która rozkłada się na złączenia (nie jestem pewien, czy się spotykają). Czy to przydatny konstrukt w...
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 ,...
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
Niech będzie klasą wszystkich zwykłych języków.REGREG\mathsf{REG} Znane jest i . Ale czy istnieje jakaś charakterystyka języków w \ mathsf {AC} ^ 0 \ cap \ mathsf {REG} ?AC0⊄REGAC0⊄REG\mathsf{AC}^0 \not\subset \mathsf{REG}REG⊄AC0REG⊄AC0\mathsf{REG} \not\subset...
Pytanie jest proste i bezpośrednie: w przypadku ustalonego , ile (różnych) języków jest akceptowanych przez DFA o rozmiarze n (tj. N stanów)? Formalnie stwierdzę to:nnnnnnnnn Zdefiniuj DFA jako , gdzie wszystko jest jak zwykle, a δ : Q × Σ → Q jest funkcją (być może częściową). Musimy to...
Zastanawiałem się, czy specyfikacja JSON definiuje zwykły język. Wydaje się to dość proste, ale nie jestem pewien, jak sam to udowodnić. Powodem, dla którego pytam, jest to, że zastanawiałem się, czy można użyć wyrażeń regularnych, aby skutecznie przetworzyć JSON. Czy ktoś z wystarczającą liczbą...
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane...
Rozważmy język składający się ze wszystkich ciągów -lettera nad tak aby żadne dwie litery nie były równe:L k - d i s t i n c tLk−distinctL_{k-distinct} k kkΣΣ\Sigma L k - d i s t i n c t : = { w = σ 1 σ 2 . . . σ k ∣ ∀ i ∈ [ k ] : σ i ∈ Σ and ∀ j ≠ i : σ j ≠ σ i...
Kontekst: relacje między logiką a automatami Twierdzenie Büchiego stwierdza, że logika Monadic drugiego rzędu nad łańcuchami (MSO) przechwytuje klasę zwykłych języków. Dowód faktycznie pokazuje, że egzystencjalne MSO ( ∃MSO∃MSO\exists\text{MSO} lub EMSO ) nad łańcuchami wystarczy do...
W teorii automatów (automaty skończone, automaty wypychające, ...) i złożoności występuje pojęcie „dwuznaczności”. Automat jest dwuznaczny, jeśli istnieje słowo z co najmniej dwoma odrębnymi przebiegami akceptującymi. Maszyna jest k- dwuznaczna, jeśli dla każdego słowa w zaakceptowanego przez...
Jednoznaczne automaty skończone (UFA) są specjalnym typem niedeterministycznych automatów skończonych (NFA). NFA jest nazywany jednoznacznym, jeśli każde słowo ma co najwyżej jedną ścieżkę akceptującą.w ∈ Σ∗w∈Σ∗w\in \Sigma^* Oznacza to, .D F.A ⊂ UfaA ⊂ NfaZArefaZA⊂UfaZA⊂N.faZADFA\subset...
Mówimy, że NFA jest stale niejednoznaczny, jeśli istnieje tak że każde słowo jest akceptowane przez lub (dokładnie) ścieżek.MMMk∈Nk∈Nk\in \mathbb{N}w∈Σ∗w∈Σ∗w\in \Sigma^*000kkk Jeśli automat jest stale niejednoznaczny dla , wówczas nazywa się Jednoznacznym FA (UFA).MMMk=1k=1k=1MMM Niech będzie...
Czytam „ Łączenie zwykłych języków i złożoności opisowej ” Galiny Jiraskowej z 2009 r. Na temat złożoności państwa wynikającej z połączenia dwóch zwykłych języków (Galiny Jiraskowej), ale nie rozumiem, jakie byłyby praktyczne implikacje złożoności państwa . Pierwszą trywialną myślą, która mnie...
Według Zoo Złożoności , Reg⊆NC1Reg⊆NC1\mathsf{Reg} \subseteq \mathsf{NC^1} i wiemy, że RegReg\mathsf{Reg} nie może się liczyć, więc TC0⊈RegTC0⊈Reg\mathsf{TC^0} \not\subseteq \mathsf{Reg} . Jednakże nie mówi, czy Reg⊆TC0Reg⊆TC0\mathsf{Reg} \subseteq \mathsf{TC^0} czy nie. Ponieważ nie znamy...