Pytania otagowane jako fl.formal-languages

języki formalne, gramatyka, teoria automatów

2
Zwykły kontra TC0
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 NC1⊈TC0NC1⊈TC0\mathsf{NC^1}\not\subseteq\mathsf{TC^0} , nie znamy również Reg⊈TC0Reg⊈TC0\mathsf{Reg} \not\subseteq \mathsf{TC^0} . Czy jest kandydatem do problemu w , który nie …
2
Czy automaty XOR (NXA) dla języków skończonych korzystają z cykli?
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 NFA, który nie zawiera żadnych cykli (jeśli cykl był …
4
Czy eta-równoważność funkcji jest zgodna z sekwencją Haskella?
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 …
3
Znaczenie złożoności stanu w automatach i językach regularnych?
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 uderzyła, było to, że większa złożoność wymagałaby więcej czasu …
1
Wystarczające warunki dla prawidłowości języka bezkontekstowego
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 powinno „w jakiś sposób …
1
Dolne granice wielkości CFG dla określonych języków skończonych
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 „musiałby” mieć rozmiar . Jesteśmy więc zainteresowani asymptotycznym rozmiarem najmniejszych CFG dla języków.L.nL.nL_nL.nL.nL_n{ 1 …
2
Wydajny algorytm do aktualizowania drzewa analizy
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 czy istnieją algorytmy określające zakres do ponownej analizy i odpowiednio …
1
Czy {ww '| HamDist (w, w ')> 1} bez kontekstu?
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 kontekstu?L={ww′∣w,w′∈{0,1}∗∧|w|=|w′|∧HamDist(w,w′)>1}L={ww′∣w,w′∈{0,1}∗∧|w|=|w′|∧HamDist(w,w′)>1}L = \{ ww' \mid w,w' \in \{0,1\}^* \land |w|=|w'| \land HamDist(w,w')>1 \} Tutaj wymagamy, aby dwa struny różniły się co najmniej w dwóch pozycjach (odległość …
1
Odległość między zwykłymi językami
Chcę zdefiniować pojęcie „bliskości” między dwoma regularnymi językami skończonych słów w (i / lub nieskończonych słów w Σ ω ). Podstawową ideą jest to, że chcemy, aby dwa języki były blisko siebie, jeśli nie różnią się wieloma słowami. Możemy również w jakiś sposób wykorzystać odległość edycji ... Nie mogłem znaleźć …
4
(N) DFA z tymi samymi stanami początkowymi / akceptującymi
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 samo dotyczy języków rozpoznawanych przez niedeterministyczne automaty posiadające ten …
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.