Powiedzmy, że mam duży blok kodu, który już sprawdziłem i przeanalizowałem. Załóżmy, że zmienia się tylko jedna postać; Chciałbym zaktualizować parsowanie, ale ponieważ modyfikacja jest bardzo niewielka w porównaniu do całości, chciałbym wiedzieć, czy nie można ponownie przeanalizować całości, ale...
Niedeterministyczne automaty Xor (NXA) są składniowo NFA, ale mówi się, że słowo jest akceptowane przez NXA, jeśli ma nieparzystą liczbę ścieżek akceptacji (zamiast co najmniej jednej ścieżki akceptacji w przypadku NFA). Łatwo zauważyć, że dla skończonego języka regularnego LLL istnieje minimalny...
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...
Lemat: Zakładając, że równoważność eta istnieje (\x -> ⊥) = ⊥ :: A -> B. Dowód: ⊥ = (\x -> ⊥ x)przez eta-równoważność i (\x -> ⊥ x) = (\x -> ⊥)redukcję pod lambda. Raport Haskell 2010, rozdział 6.2 określa seqfunkcję na podstawie dwóch równań: seq :: a -> b -> b seq ⊥ b =...
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...
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...
Czy standardowa maszyna z dwoma licznikami ( ) może następujące instrukcje:c1,c2c1,c2c_1,c_2 1) ADD 1 to c_i, GOTO label_j 2) IF c_i = 0 GOTO label_j, OTHERWISE SUB 1 to c_i and GOTO label_k 3) GOTO label_j 4) HALT and ACCEPT|REJECT wybierz następujący język: L={n2∣n≥1}L={n2∣n≥1}L = \{ n^2 \mid...
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
Co wiadomo o klasie języków rozpoznawanych przez automaty skończone posiadające ten sam stan początkowy i akceptacji? Jest to właściwy podzbiór zwykłych języków (ponieważ każdy taki język zawiera pusty ciąg znaków), ale jak bardzo jest słaby? Czy istnieje prosta charakterystyka algebraiczna? To...
Obecnie prowadzę badania nad językiem formalnym, które obejmują klasy języków powyżej zwykłego, ale poniżej kontekstowego. Patrzę na takie rzeczy, jak maszyny zliczające z odwróceniem, maszyny liczące na jednym stosie, deterministyczne CFL itp. Zastanawiam się, czy ktokolwiek wie o dobrej książce...
Jest to prawdopodobnie dość proste, ale weź pod uwagę standardowy problem z korespondencją: Biorąc pod uwagę, i β 1 , ... , β N , znaleźć sekwencję indeksów i 1 , ... , i K tak, że a i 1 ⋯ α i K = β i 1 ⋯ β i K . Jest to oczywiście nierozstrzygalne.α1, … , ΑN.α1,…,αN\alpha_1, \ldots, \alpha_Nβ1, …...
Czy ktoś może podać przykład dwóch równoważnych (rozpoznających ten sam język) minimalnych niedeterministycznych automatów (NFA), które nie są
Przeniosłem to pytanie z stackoverflow, gdzie id nie otrzymał odpowiedzi. Mieliśmy podobne pytanie, czy JSON jest regularny : JSON i XML są często nazywane językami bezkontekstowymi - oba są określone głównie przez gramatykę formalną w EBNF. Jednak dotyczy to tylko JSON zdefiniowanego w RFC 4329,...
Dobrze wiadomo, że uzupełnienie jest pozbawione kontekstu. Ale co z dopełnieniem ?{ww∣w∈Σ∗}{ww∣w∈Σ∗}\{ ww \mid w\in \Sigma^*\}{www∣w∈Σ∗}{www∣w∈Σ∗}\{ www \mid w\in
Powiedzmy, że mamy język , ale nie wiemy, jakie ciągi znaków są w rzeczywistości częścią tego języka. Wszystko, co ma, to skończony widok języka: skończony zestaw ciągów A \ subseteq L , o których wiadomo, że są w języku, oraz skończony zestaw ciągów B \ subseteq (\ Sigma ^ * \ setminus L), które...
Greibach pokazowo zdefiniował język , tzw niedeterministycznych wersję z , tak że każdy CFL odwrotna morficznego obraz . Czy istnieje podobne stwierdzenie dotyczące DCFL, być może z dopuszczalnymi ograniczeniami morfizmów?HHHD2D2D_2HHH (Patrz np. M. Autebert, J. Berstel i L. Boasson. Języki...
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...
Szukam języka L o następujących właściwościach: L nie powinien być pozbawiony kontekstu. Uzupełnienie L nie powinno być pozbawione kontekstu. (Wszystko, co widzisz w podręcznikach jako główny przykład języków bezkontekstowych, wydaje się nie spełniać tego drugiego wymogu). L nie powinien być zbyt...
EDYCJA (autor: Tara B): Nadal byłbym zainteresowany odniesieniem do dowodu na to, ponieważ musiałem to udowodnić na własne potrzeby. Szukam dowodu Twierdzenia 4, który pojawia się w tym artykule: Nieskończona hierarchia skrzyżowań języków bezkontekstowych autorstwa Liu i Weinera. Twierdzenie...